#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
struct Line {
    mutable ll m, b, p;
    bool operator<(const Line &o) const { return m < o.m; }
    bool operator<(const ll &x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> { // upper convex hull.
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    const ll inf = LLONG_MAX;
    ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) {
            x->p = inf;
            return false;
        }
        if (x->m == y->m)
            x->p = x->b > y->b ? inf : -inf;
        else
            x->p = div(y->b - x->b, x->m - y->m);
        return x->p >= y->p;
    }
    void add(ll m, ll b) {
        auto z = insert({m, b, 0}), y = z++, x = y;
        while (isect(y, z))
            z = erase(z);
        if (x != begin() && isect(--x, y))
            isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.m * x + l.b;
    }
};

const ll is_query = -(1LL << 60);
struct Line2 {
    ll m, b;
    mutable function<const Line2 *()> succ;
    bool operator<(const Line2 &rhs) const {
        if (rhs.b != is_query)
            return m < rhs.m;
        const Line2 *s = succ();
        if (!s)
            return 0;
        ll x = rhs.m;
        return b - s->b < (s->m - m) * x;
    }
};
struct HullDynamic : public multiset<Line2> { // will maintain upper hull for maximum
    bool bad(iterator y) {
        auto z = next(y);
        if (y == begin()) {
            if (z == end())
                return 0;
            return y->m == z->m && y->b <= z->b;
        }
        auto x = prev(y);
        if (z == end())
            return y->m == x->m && y->b <= x->b;
        return (x->b - y->b) * (z->m - y->m) >= (y->b - z->b) * (y->m - x->m);
    }
    void insert_line(ll m, ll b) {
        auto y = insert({m, b});
        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
        if (bad(y)) {
            erase(y);
            return;
        }
        while (next(y) != end() && bad(next(y)))
            erase(next(y));
        while (y != begin() && bad(prev(y)))
            erase(prev(y));
    }
    ll eval(ll x) {
        auto l = *lower_bound({x, is_query});
        return l.m * x + l.b;
    }
};
typedef long double ld;
const ld inf = 1e18;

struct chtDynamic {
    struct line {
        ll m, b;
        ld x;
        ll val;
        bool isQuery;
        line(ll _m = 0, ll _b = 0) : m(_m), b(_b), val(0), x(-inf), isQuery(false) {}

        ll eval(ll x) const { return m * x + b; }
        bool parallel(const line &l) const { return m == l.m; }
        ld intersect(const line &l) const { return parallel(l) ? inf : 1.0 * (l.b - b) / (m - l.m); }
        bool operator<(const line &l) const {
            if (l.isQuery)
                return x < l.val;
            else
                return m < l.m;
        }
    };

    set<line> hull;
    typedef set<line>::iterator iter;

    bool cPrev(iter it) { return it != hull.begin(); }
    bool cNext(iter it) { return it != hull.end() && next(it) != hull.end(); }

    bool bad(const line &l1, const line &l2, const line &l3) { return l1.intersect(l3) <= l1.intersect(l2); }
    bool bad(iter it) { return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it)); }

    iter update(iter it) {
        if (!cPrev(it))
            return it;
        ld x = it->intersect(*prev(it));
        line tmp(*it);
        tmp.x = x;
        it = hull.erase(it);
        return hull.insert(it, tmp);
    }

    void addLine(ll m, ll b) {
        line l(m, b);
        iter it = hull.lower_bound(l);
        if (it != hull.end() && l.parallel(*it)) {
            if (it->b < b)
                it = hull.erase(it);
            else
                return;
        }

        it = hull.insert(it, l);
        if (bad(it))
            return (void)hull.erase(it);

        while (cPrev(it) && bad(prev(it)))
            hull.erase(prev(it));
        while (cNext(it) && bad(next(it)))
            hull.erase(next(it));

        it = update(it);
        if (cPrev(it))
            update(prev(it));
        if (cNext(it))
            update(next(it));
    }

    ll query(ll x) const {
        if (hull.empty())
            return -inf;
        line q;
        q.val = x, q.isQuery = 1;
        iter it = --hull.lower_bound(q);
        return it->eval(x);
    }
} ds;
LineContainer cht1;
HullDynamic cht2;
chtDynamic cht3;
const int NUM_INSERTS = 1e7;
const int NUM_QUERIES = 1e7;
vector<int> res1, res2, res3;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<array<int, 2>> lines;
    vector<int> queries;
    for (int i = 0; i < NUM_INSERTS; i++)
        lines.push_back({rand(), rand()});
    for (int i = 0; i < NUM_QUERIES; i++)
        queries.push_back(rand());

    clock_t begin;
    begin = clock();
    for (auto i : lines)
        cht1.add(i[0], i[1]);
    for (auto i : queries)
        res1.push_back(cht1.query(i));

    cout << "LineContainer: " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
    begin = clock();
    for (auto i : lines)
        cht2.insert_line(i[0], i[1]);
    for (auto i : queries)
        res2.push_back(cht2.eval(i));

    cout << "HullDynamic:   " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;
    begin = clock();
    for (auto i : lines)
        cht3.addLine(i[0], i[1]);
    for (auto i : queries)
        res3.push_back(cht3.query(i));

    cout << "chtDynamic:    " << (double)(clock() - begin) / CLOCKS_PER_SEC << endl;

    // for (int i = 0; i < res1.size(); i++)
    //     assert(res1[i] == res2[i]);
}