struct line
{
    long long k, b;
};
line t[(1 << 21)];
long long f(line a, int x)
{
    return x * a.k + a.b;
}

void add(line nw, int v = 1, int l = 0, int r = 1e6)
{
    int m = l + r >> 1;
    bool lef = f(nw, l) < f(t[v], l);
    bool mid = f(nw, m) < f(t[v], m);
    if (mid)
        swap(t[v], nw);
    if (l == r)
        return;
    if (lef != mid)
        add(nw, 2 * v, l, m);
    else
        add(nw, 2 * v + 1, m + 1, r);
}
long long get(int pos, int v = 1, int l = 0, int r = 1e6)
{
    if (l == r)
        return f(t[v], pos);
    int m = l + r >> 1;
    long long val = f(t[v], pos);
    if (pos <= m)
        return min(get(pos, 2 * v, l, m), val);
    else
        return min(get(pos, 2 * v + 1, m + 1, r), val);
}