Untitled

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int tt, tc;

const int MAXA = 2e6 + 9;
const int DELTA = 1e6;

typedef long long ftype;
typedef complex<ftype> point;
#define x real
#define y imag

ftype dot(point a, point b) {
    return (conj(a) * b).x();
}

ftype f(point a,  ftype X) {
    return dot(a, {X, 1});
}

point line[MAXA << 2];
vector<vector<tuple<int, point, point>>> st;

void add_line(point nw, int v = 1, int l = 0, int r = MAXA - 5) {
    int m = (l + r) / 2;
    bool lef = f(nw, l - DELTA) > f(line[v], l - DELTA);
    bool mid = f(nw, m - DELTA) > f(line[v], m - DELTA);
    if(mid) {
        swap(line[v], nw); // line[v] = nw
        st.back().emplace_back(v, line[v], nw);
    }
    if(r - l == 1) {
        return;
    } else if(lef != mid) {
        add_line(nw, 2 * v, l, m);
    } else {
        add_line(nw, 2 * v + 1, m, r);
    }
}

void roll_back() {
    auto V = st.back();
    st.pop_back();

    reverse(V.begin(), V.end());
    for (auto& [v, X, y] : V) {
        swap(line[v], X);
    }
}

ftype get(int X, int v = 1, int l = 0, int r = MAXA - 5) {
    int m = (l + r) / 2;
    if(r - l == 1) {
        return f(line[v], X);
    } else if(X < m) {
        return max(f(line[v], X), get(X, 2 * v, l, m));
    } else {
        return max(f(line[v], X), get(X, 2 * v + 1, m, r));
    }
}

void solve() {
    // add line (x, y)
    // query (p) : max_{x, y} (x * p + y)
    add_line(1, 2);
    add_line(5, 1);
    cout << get(1) << "\n";
	// int n = 1;
    // int index = 0;
    // vector<vector<int>> g(n);
    // vector<ll> X(n), Y(n);

    // vector<pair<int, ll>> ask; // first is vertex, second is value
    // int q;
    // cin >> q;
    // while (q--) {
    //     int type;
    //     cin >> type;
    //     if (type == 1) {
    //         cin >> index;
    //     } else if (type == 2) {
    //         ll XX, YY;
    //         cin >> XX >> YY;
    //         int new_index;
    //         cin >> new_index;
    //         g[index].push_back(new_index);
    //         X.push_back(XX);
    //         Y.push_back(YY);
    //         n++;
    //         g.push_back(vector<int>());
    //         index = new_index;
    //     } else {
    //         ll V;
    //         cin >> V;
    //         ask.emplace_back(index, V);
    //     }
    // }

    // vector<vector<int>> queries(n);
    // q = ask.size();
    // vector<ll> query_ans(q);

    // for (int i = 0; i < q; i++) {
    //     queries[ask[i].first].push_back(i);
    // }

    // function<void(int)> dfs = [&](int v) {
    //     point nw(X[v], Y[v]);
    //     st.push_back(vector<tuple<int, point, point>>());
    //     add_line(nw);

    //     for (int query : queries[v]) query_ans[query] = get(ask[query].second);

    //     for (int u : g[v]) dfs(u);

    //     roll_back();
    // };
    // for (ll val : query_ans) cout << val << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	tt = 1, tc = 1;
	// cin >> tt;
	while (tt--) {
		solve();
		tc++;
	}
}