Tý có một công ty bất động sản đang cần mua \(N\) mảnh đất để xây dựng khu đô thị. Mỗi mảnh đất có chiều rộng \(w_i\) và chiều dài \(h_i\).

Do chính sách ưu đãi, công ty có thể mua nhiều mảnh đất cùng lúc. Khi mua một nhóm các mảnh đất, chi phí phải trả bằng tích của chiều rộng lớn nhất và chiều dài lớn nhất trong nhóm đó.

Công ty muốn chia các mảnh đất thành một số nhóm (mỗi mảnh thuộc đúng một nhóm) sao cho tổng chi phí mua đất là nhỏ nhất.

Hãy tính tổng chi phí nhỏ nhất đó.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i, h_i\) (\(1 \le w_i, h_i \le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng chi phí nhỏ nhất.

Ví dụ

Input:

4
100 1
15 15
20 5
1 100

Output:

500

Giải thích: Nhóm 1: \((100,1)\) và \((1,100)\) chi phí \(100 \times 100 = 10000\). Nhóm 2: \((15,15)\) và \((20,5)\) chi phí \(20 \times 15 = 300\). Tổng \(10300\). Nhóm tối ưu: \((100,1)\) mua riêng (100), \((1,100)\) mua riêng (100), \((15,15)+(20,5)\) mua chung (300) → tổng \(500\).

Ràng buộc

• Subtask 1 (30%): \(N \le 2000\).
• Subtask 2 (30%): \(N \le 10^4\).
• Subtask 3 (40%): \(N \le 10^5\).