Subtask 1: Duyệt trâu

Subtask 2: Vì ~w_i = h_i~ nên ta không cần quan tâm tới hướng xoay của nó. Để thu được kết quả tối ưu, ta đơn giản chỉ cần đặt hai khối với kích thước lớn nhất nằm ở hai biên. Lúc này, việc sắp xếp những khối còn lại cũng không thay đổi lượng nước thu được sau cùng.

Độ phức tạp: ~O(N)~.

Subtask 3: Giả sử ~w_i \geq h_i~ đối với mọi khối chữ nhật. Ta có thể áp dụng thuật toán tham lam sau:

• Đầu tiên, đặt hai khối chữ nhật cao nhất nằm ở hai biên.

• Sau đó, nếu hai khối chữ nhật ở hai biên có chiều dài lớn hơn chiều cao, thực hiện xoay hình lại. Đối với những khối chữ nhật nằm trong thì làm điều ngược lại, nếu chiều cao lớn hơn chiều rộng thì xoay hình lại.

Dựa vào thuật toán tham lam trên, ta có thể cố định khối hình chữ nhật nằm ở biên, chọn hướng xoay giống như cách đã trình bày ở trên. Khi đó, ta chỉ việc tính lượng nước thu được trong ~O(N)~.

Độ phức tạp: ~O(N ^ 3)~.

Subtask 4: Ta có thể cải tiến từ Subtask 3 như sau: Việc tính lượng nước thu được ta có thể cải tiến lên thành ~O(1)~. Gọi ~Area(i, j)~ là lượng nước thu được nếu chọn ~i~ và ~j~ làm khối chữ nhật ở hai biên.

Khi đó ta có công thức:

$$\text{sumw} = \sum_{k=1}^n w_k$$ $$\text{summul} = \sum_{k=1}^n w_k \cdot h_k$$

$$\ Area(i, j) = w_i h_i + w_j h_j + \min(w_i, w_j) \cdot (\text{sumw} - w_i - w_j) - \text{summul}.$$

Độ phức tạp: ~O(N ^ 2)~.

Subtask 5: Từ subtask 4 ta có thể sắp xếp lại các khối chữ nhật theo ~w~ tăng dần. Với ~i < j~, ta có:

~Area(i, j) = w_i \cdot h_i + w_j \cdot h_j + w_i \cdot (sum_w - w_i - w_j) - summul~ ~= w_i \cdot (h_i + sum_w - w_i) + w_j \cdot h_j - w_i \cdot w_j - summul.~

Áp dụng convex hull trick để tìm ra ~Area(i, j)~ lớn nhất.

Độ phức tạp: ~O(N \cdot log(N)).~

/*
Subtask description: No additional constraints
*/

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>

using namespace std;

const int N = 3e5 + 5;

int n; 

struct rect{
    int w, h;
};

struct line{
    int a, b;

    inline int f(int x){
        return a * x + b;
    }

    bool useless(const line &nxt, const line &pre){
        double it1 = (b - pre.b) / (pre.a - a);
        double it2;
        if(nxt.a != a){
            it2 = (b - nxt.b) / (nxt.a - a);
            return it2 <= it1;
        } else{
            return nxt.b >= b;
        }
    }
};

vector<rect> a;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);    cout.tie(0);

    #define TASK "rainfall"
    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }

    cin >> n;

    int s = 0, sw = 0, ans = 0;
    for(int i = 0; i < n; i++){
        int w, h; cin >> w >> h;
        if(w < h) swap(w, h);
        s += w * h, sw += w;
        a.push_back({w, h});
    }

    sort(a.begin(), a.end(), [](const rect &x, const rect &y){
        return x.w < y.w || (x.w == y.w && x.h < y.h);
    });
    vector<rect> b;
    if(a[0].w != a[1].w) b.push_back(a[0]);
    for(int i = 1; i < n; i++){
        ans = max(ans, a[i].w * a[i].h + a[i - 1].w * a[i - 1].h + (sw - a[i].w - a[i - 1].w) * min(a[i].w , a[i - 1].w) - s);
        if(i == n - 1 || a[i + 1].w != a[i].w) b.push_back(a[i]);
    }
    a = b, n = a.size(); b.clear();
    sort(a.begin(), a.end(), [](const rect &x, const rect &y){
        return x.w > y.w;
    });

    /*
    Max W[i] * H[i] + W[j] * H[j] - S + w[i] * sw - w[i] ^ 2 - w[i] * w[j]
    */

    deque<line> dq;
    for(int i = 0; i < n; i++){
        while(dq.size() > 1 && dq.front().f(a[i].w) <= dq[1].f(a[i].w)) dq.pop_front();
        if(dq.size()){
            int contains = dq.front().f(a[i].w) + a[i].w * a[i].h + a[i].w * (sw - a[i].w) - s;
            ans = max(ans, contains);
        }

        line nw = {-a[i].w, a[i].h * a[i].w};
        while(dq.size() > 1 && dq.front().useless(nw, dq[1])) dq.pop_front();
        dq.push_front(nw);
    }

    cout << ans << '\n';
    return 0;
}