#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

// =====================================================================
// COLLECTION OF CONVEX HULL TRICK (CHT) / LINE CONTAINER ALGORITHMS
// =====================================================================
//
// This file provides multiple implementations of data structures that
// store linear functions y = m*x + b and support:
//   1. Adding a line.
//   2. Querying the minimum (or maximum) y at a given x.
//
// Use cases:
//   - Optimizing DP transitions of the form:
//       dp[i] = min_j ( dp[j] + a[i]*b[j] + c[j] )
//     where each j is a line (m = b[j], b = dp[j] + c[j]) and
//     a[i] is the query x.
//
// Each structure below has its own strengths and constraints.
// Read the comments above each to choose the right one.
// =====================================================================

// =====================================================================
// 1) LineContainer (KACTL implementation)
//    =====================================
//    General-purpose, supports adding lines in ANY order and querying
//    at ANY x.  Uses a multiset to maintain the lower envelope.
//
//    HOW TO USE:
//       LineContainer cht;
//       cht.add(2, 5);      // adds y = 2*x + 5
//       cht.add(-1, 3);     // adds y = -1*x + 3
//       ll ans = cht.query(4);  // returns minimum y at x = 4
//
//    For MAXIMUM queries: store lines as (-m, -b) and negate the result.
//
//    TIME COMPLEXITY:
//       add(line)  : O(log N) amortized.
//       query(x)   : O(log N).
//
//    CONSTRAINTS:
//       - m, b, x fit in 'long long' (up to ≈9e18).
//       - Uses 'long double' only for intersection checks internally,
//         but the result is computed in integer arithmetic.
//       - If coordinates can exceed 1e9, multiplication may overflow
//         'long long' – consider using '__int128' for the result
//         (modify query to return __int128 if needed).
// =====================================================================
struct LineContainer {
    struct Line {
        mutable ll m, b, p;   // y = m*x + b,  p = first x where this line is optimal
        bool operator<(const Line& o) const { return m < o.m; }
        bool operator<(ll x) const { return p < x; }
    };

    multiset<Line, less<>> hull;
    static const ll inf = LLONG_MAX;

    // floor division for possibly negative numbers (KACTL style)
    ll div(ll a, ll b) {
        return a / b - ((a ^ b) < 0 && a % b);
    }

    // Check if line y (pointed by iterator y) is made obsolete by x and z.
    // Returns true if y should be removed.
    bool isect(typename multiset<Line, less<>>::iterator x,
               typename multiset<Line, less<>>::iterator y) {
        if (y == hull.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;
    }

    // Add a new line y = m*x + b.
    void add(ll m, ll b) {
        auto z = hull.insert({m, b, 0});
        auto y = z++;
        auto x = y;

        // Remove lines to the right that become obsolete
        while (isect(y, z)) z = hull.erase(z);

        // Remove lines to the left if the new line makes them obsolete
        if (x != hull.begin() && isect(--x, y)) {
            isect(x, y = hull.erase(y));
        }

        // Further clean-up to the left
        while ((y = x) != hull.begin() && (--x)->p >= y->p) {
            isect(x, hull.erase(y));
        }
    }

    // Query the minimum y at x.
    ll query(ll x) const {
        auto it = hull.lower_bound(x);
        if (it == hull.begin()) return it->m * x + it->b;
        --it;
        return it->m * x + it->b;
    }
};

// =====================================================================
// 2) Dynamic Li Chao Tree (Node‑based)
//    ==================================
//    Works over a fixed integer interval [L, R] of possible x‑coordinates.
//    Nodes are created on the fly, so no coordinate compression needed.
//
//    HOW TO USE:
//       DynamicLiChao cht(0, 1e9);   // x in [0, 1e9]
//       cht.add({2, 5});             // y = 2*x + 5
//       ll ans = cht.query(4);       // minimum y at x = 4
//
//    TIME COMPLEXITY:
//       add(line) : O(log (R - L))
//       query(x)  : O(log (R - L))
//
//    CONSTRAINTS:
//       - L, R fit in 'long long'.
//       - Memory is O(number_of_lines * log(R-L)).
//       - Works well for large ranges (e.g., up to 1e18) because depth is ~60.
// =====================================================================
struct DynamicLiChao {
    struct Line {
        ll m, b;
        ll get(ll x) const { return m * x + b; }
    };

    struct Node {
        Line line;
        Node *left, *right;
        Node(Line l) : line(l), left(nullptr), right(nullptr) {}
    };

    Node* root;
    ll l_range, r_range;
    static const ll INF = 4e18;

    DynamicLiChao(ll l, ll r) : l_range(l), r_range(r) {
        root = new Node({0, INF});   // dummy line that returns INF
    }

    void add(Line nw) { add(nw, root, l_range, r_range); }

    void add(Line nw, Node*& node, ll l, ll r) {
        if (!node) {
            node = new Node(nw);
            return;
        }
        ll mid = l + (r - l) / 2;
        Line cur = node->line;

        // Keep the better line at mid in the node
        if (nw.get(mid) < cur.get(mid)) {
            swap(node->line, nw);
            cur = node->line;   // now cur is the line that is better at mid
        }
        if (l == r) return;

        // The worse line (nw) may be better on one side
        if (nw.get(l) < cur.get(l)) {
            add(nw, node->left, l, mid);
        } else if (nw.get(r) < cur.get(r)) {
            add(nw, node->right, mid + 1, r);
        }
        // else nw is never better in this interval
    }

    ll query(ll x) { return query(root, x, l_range, r_range); }

    ll query(Node* node, ll x, ll l, ll r) {
        if (!node) return INF;
        ll res = node->line.get(x);
        if (l == r) return res;
        ll mid = l + (r - l) / 2;
        if (x <= mid) return min(res, query(node->left, x, l, mid));
        else return min(res, query(node->right, x, mid + 1, r));
    }
};

// =====================================================================
// 3) Li Chao Tree with Coordinate Compression
//    =========================================
//    Used when all possible query x‑values are known in advance.
//    Sorts and compresses them, then builds a segment tree over indices.
//
//    HOW TO USE:
//       vector<ll> xs = {0, 3, 5, 10};   // all x that will be queried
//       LiChaoCompressed cht(xs);
//       cht.add({2, 5});
//       cout << cht.query(3);   // 3 must be in xs
//
//    TIME COMPLEXITY:
//       add(line) : O(log M), where M = number of distinct x
//       query(x)  : O(log M)
//
//    CONSTRAINTS:
//       - Query points must be known at construction.
//       - Memory is O(4*M), faster and lighter than dynamic version.
// =====================================================================
struct LiChaoCompressed {
    struct Line {
        ll m, b;
        ll get(ll x) const { return m * x + b; }
    };

    vector<ll> xs;               // sorted unique coordinates
    vector<Line> tree;
    int n;
    static const ll INF = 4e18;

    LiChaoCompressed(vector<ll> _xs) : xs(_xs) {
        sort(xs.begin(), xs.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        n = (int)xs.size();
        tree.assign(4 * n, {0, INF});
    }

    void add(Line nw) { add(nw, 1, 0, n - 1); }

    void add(Line nw, int node, int l, int r) {
        int mid = (l + r) / 2;
        ll x_l = xs[l], x_m = xs[mid], x_r = xs[r];
        Line cur = tree[node];

        if (nw.get(x_m) < cur.get(x_m)) {
            swap(tree[node], nw);
            cur = tree[node];
        }
        if (l == r) return;

        if (nw.get(x_l) < cur.get(x_l)) {
            add(nw, node * 2, l, mid);
        } else if (nw.get(x_r) < cur.get(x_r)) {
            add(nw, node * 2 + 1, mid + 1, r);
        }
    }

    ll query(ll x) {
        int idx = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        if (idx == n || xs[idx] != x) return INF;   // x not found
        return query(1, 0, n - 1, idx);
    }

    ll query(int node, int l, int r, int idx) {
        ll res = tree[node].get(xs[idx]);
        if (l == r) return res;
        int mid = (l + r) / 2;
        if (idx <= mid) return min(res, query(node * 2, l, mid, idx));
        else return min(res, query(node * 2 + 1, mid + 1, r, idx));
    }
};

// =====================================================================
// 4) Monotonic CHT (Deque‑based)
//    ============================
//    Fastest O(1) amortized, but requires:
//       - Slopes (m) added in strictly increasing (or decreasing) order.
//       - Query x in strictly increasing (or decreasing) order.
//    Use this only when the DP transition has these monotonic properties.
//
//    HOW TO USE:
//       MonoCHT cht;               // slopes must be added increasing
//       cht.add(2, 5);             // y = 2*x + 5
//       cht.add(3, 1);             // 3 > 2, valid
//       ll ans = cht.query(4);     // next query x must be >= 4
//
//    TIME COMPLEXITY:
//       add(line) : O(1) amortized
//       query(x)  : O(1) amortized
//
//    CONSTRAINTS:
//       - Slopes strictly increasing (for minimum queries).
//       - Queries non‑decreasing.
//       - Use __int128 in bad() to avoid overflow when slopes/intercepts are large.
// =====================================================================
struct MonoCHT {
    vector<ll> M, B;
    int ptr = 0;

    // Check if line2 is unnecessary given line1 and line3.
    // For minimum CHT with increasing slopes.
    bool bad(ll m1, ll b1, ll m2, ll b2, ll m3, ll b3) {
        // (b3 - b1) * (m1 - m2) <= (b2 - b1) * (m1 - m3)
        return (__int128)(b3 - b1) * (m1 - m2) <= (__int128)(b2 - b1) * (m1 - m3);
    }

    // Add a line y = m*x + b. Slopes must be increasing.
    void add(ll m, ll b) {
        // If same slope, keep the smaller intercept.
        while (!M.empty() && M.back() == m) {
            if (B.back() <= b) return;
            M.pop_back(); B.pop_back();
        }
        // Remove last line if it becomes obsolete.
        while (M.size() >= 2 &&
               bad(M[M.size()-2], B[B.size()-2], M.back(), B.back(), m, b)) {
            M.pop_back(); B.pop_back();
        }
        M.push_back(m);
        B.push_back(b);
        if (ptr >= (int)M.size()) ptr = (int)M.size() - 1;
    }

    // Query the minimum y at x. x must be non‑decreasing.
    ll query(ll x) {
        while (ptr + 1 < (int)M.size() &&
               M[ptr] * x + B[ptr] >= M[ptr + 1] * x + B[ptr + 1]) {
            ptr++;
        }
        return M[ptr] * x + B[ptr];
    }
};

// =====================================================================
// 5) Converting to MAXIMUM queries
//    ==============================
//    To find the maximum, store lines with slopes and intercepts
//    multiplied by -1, then negate the query result.
//
//    Example:
//       LineContainer cht;
//       cht.add(-2, -5);          // stores -y for y = 2*x + 5
//       ll max_val = -cht.query(4); // returns max(2*4+5, ...)
// =====================================================================

// =====================================================================
// 6) Common DP optimization pattern
//    ===============================
//    DP[i] = min_j ( DP[j] + A[i] * B[j] + C[j] )
//
//    Treat each j as a line: m = B[j], b = DP[j] + C[j].
//    Query at x = A[i] to get DP[i].
//
//    Example skeleton:
//       LineContainer cht;
//       cht.add(B[0], C[0]);    // assuming DP[0] = 0
//       for (int i = 1; i < n; i++) {
//           dp[i] = cht.query(A[i]);
//           cht.add(B[i], dp[i] + C[i]);
//       }
// =====================================================================

// =====================================================================
// EXAMPLE USAGE (can be removed)
// =====================================================================
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Test LineContainer
    LineContainer cht;
    cht.add(1, 0);   // y = x
    cht.add(0, 5);   // y = 5
    cout << cht.query(3) << "\n";   // min(3,5) = 3

    // Test DynamicLiChao
    DynamicLiChao dcht(0, 10);
    dcht.add({1, 0});
    dcht.add({0, 5});
    cout << dcht.query(3) << "\n";   // 3

    // Test MonoCHT (slopes increasing, queries increasing)
    MonoCHT mcht;
    mcht.add(1, 0);
    mcht.add(2, -1);   // y = 2x - 1
    cout << mcht.query(2) << "\n";   // min(2,3) = 2
    cout << mcht.query(5) << "\n";   // queries monotonic: 2 -> 5

    // Test LiChaoCompressed
    vector<ll> xs = {0, 3, 5, 10};
    LiChaoCompressed lc(xs);
    lc.add({1, 0});
    lc.add({0, 5});
    cout << lc.query(3) << "\n";   // 3

    // MAX query via negation
    LineContainer max_cht;
    max_cht.add(-1, 0);   // stores -y for y = x
    max_cht.add(0, -5);   // stores -y for y = 5
    cout << -max_cht.query(3) << "\n";   // max(3,5) = 5

    return 0;
}