const ll L = 1e9+7, inf = 2*L*L+7;
struct Line {
    ll a, b;
    ll operator()(ll x){return a*x+b;}
    Line():a(0),b(-inf){}
    Line(ll a, ll b):a(a), b(b){}
};
struct Node {ll l, r; Line v; Node():l(-1), r(-1), v(){}};
using LiChao = vector<Node>;

// add Line v in [l, r]
void update(LiChao& seg, Line v, ll l, ll r, ll s=-L, ll e=L, ll i=0) {
    if(e < l or r < s) return;
    if(s == e) { seg[i].v = (seg[i].v(s) > v(s))?seg[i].v:v; return; }
    
    ll mid=(s+e)>>1;
    if(l <= s && e <= r) {
        Line A = seg[i].v, B = v; if(A(s) < B(s)) swap(A, B);
        if(A(e) >= B(e)) seg[i].v = A;
        else if(A(mid) >= B(mid)) {
            seg[i].v = A;
            if(seg[i].r == -1) seg[i].r = seg.size(), seg.pb(Node());
            update(seg, B, mid+1, e, mid+1, e, seg[i].r);
        }
        else {
            seg[i].v = B;
            if(seg[i].l == -1) seg[i].l = seg.size(), seg.pb(Node());
            update(seg, A, s, mid, s, mid, seg[i].l);
        }
        return;
    }
if(seg[i].l == -1) seg[i].l = seg.size(), seg.pb(Node());
if(seg[i].r == -1) seg[i].r = seg.size(), seg.pb(Node());
    update(seg, v, l, r, s, mid, seg[i].l);
    update(seg, v, l, r, mid+1, e, seg[i].r);
}
// query max_{l_i <= x <= r_i} (a_i*x + b_i)
ll query(LiChao& seg, ll x, ll s=-L, ll e=L, ll i=0) {
    if(i == -1 or x < s or e < x) return -inf;
    if(s == e) return seg[i].v(x);
    ll mid = (s+e)>>1;
    return max({query(seg, x, s, mid, seg[i].l), query(seg, x, mid+1, e, seg[i].r), seg[i].v(x)});
}

// LiChao seg(1, Node());
// update(seg, {a, b}, l, r);
// ll v = query(seg, x);