1
2
3
4
5
6
7
8
9

<입력>
N
W1 H1
W2 H2
...
WN HN

<출력>
최소 비용

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

struct Line {
    int64 slope;
    int64 intercept;
    inline int64 value_at(int64 x) const { return slope * x + intercept; }
};

static inline bool is_redundant(const Line& l1, const Line& l2, const Line& l3) {
    // lower hull, decreasing slopes
    __int128 left  = (__int128)(l3.intercept - l1.intercept) * (l1.slope - l2.slope);
    __int128 right = (__int128)(l2.intercept - l1.intercept) * (l1.slope - l3.slope);
    return left <= right;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<pair<int64,int64>> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second; // (W, H)

    // 1) Sort by W asc; deduplicate by W keeping max H
    sort(a.begin(), a.end()); // by W asc, then H asc
    vector<pair<int64,int64>> dedup;
    dedup.reserve(n);
    for (auto &p : a) {
        if (dedup.empty() || dedup.back().first != p.first) dedup.push_back(p);
        else dedup.back().second = max(dedup.back().second, p.second);
    }

    // 2) Remove dominated rectangles: scan from large W to small W keeping strictly increasing H
    vector<pair<int64,int64>> rects; // after filtering
    rects.reserve(dedup.size());
    int64 maxH = LLONG_MIN;
    for (int i = (int)dedup.size() - 1; i >= 0; --i) {
        int64 w = dedup[i].first, h = dedup[i].second;
        if (h > maxH) {
            rects.emplace_back(w, h);
            maxH = h;
        }
    }
    reverse(rects.begin(), rects.end()); // now W increasing, H strictly decreasing

    int m = (int)rects.size();
    if (m == 0) { cout << 0 << '\n'; return 0; }

    vector<int64> W(m + 1), H(m + 1);
    for (int i = 1; i <= m; ++i) {
        W[i] = rects[i - 1].first;
        H[i] = rects[i - 1].second;
    }

    // 3) DP with Convex Hull Trick:
    // dp[i] = min_{0 <= k < i} (dp[k] + W[i] * H[k+1])
    // Maintain lines: slope = H[k+1] (decreasing), intercept = dp[k]
    vector<int64> dp(m + 1, 0);
    deque<Line> hull;
    hull.push_back({H[1], 0}); // k = 0

    for (int i = 1; i <= m; ++i) {
        // Query at x = W[i], x is non-decreasing
        while (hull.size() >= 2 && hull[0].value_at(W[i]) >= hull[1].value_at(W[i])) {
            hull.pop_front();
        }
        dp[i] = hull.front().value_at(W[i]);

        // Insert new line for k = i: slope = H[i+1], intercept = dp[i]
        if (i + 1 <= m) {
            Line nl{H[i + 1], dp[i]};
            while (hull.size() >= 2 && is_redundant(hull[hull.size() - 2], hull[hull.size() - 1], nl)) {
                hull.pop_back();
            }
            hull.push_back(nl);
        }
    }

    cout << dp[m] << '\n';
    return 0;
}