Tý có \(N\) mảnh đất hình chữ nhật, mảnh i rộng w_i, cao \(h_i\). Chủ đất muốn bán hết tất cả các mảnh. Mỗi lần mua, người mua có thể mua một nhóm các mảnh đất, giá nhóm bằng:

\((\text{chiều rộng lớn nhất trong nhóm}) \times (\text{chiều cao lớn nhất trong nhóm})\)

Hãy chia các mảnh đất thành các nhóm (mỗi mảnh một nhóm, thứ tự tùy ý) sao cho tổng tiền thu được là nhỏ nhất (giả sử người mua luôn mua hết).

Dữ liệu vào

• Dòng đầu gồm \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dòng sau, mỗi dòng \(w_i, h_i\) (\(1 \le w_i, h_i \le 10^6\)).

Kết quả ra

• In ra tổng tiền nhỏ nhất.

Ví dụ

Input

4
2 5
4 3
3 6
1 4

Output

27

Giải thích: Sắp xếp \((4, 3)\), \((2, 5)\), \((3, 6)\), \((1, 4)\). Nhóm \((4, 3)\)+\((2, 5)\): \(max_w=4\), \(max_h=5\) → 20. Nhóm \((3, 6)\)+\((1, 4)\): \(max_w=3\), \(max_h=6\) → 18. Tổng 38. Tối ưu: \((4, 3)\) riêng 12, \((2, 5)\)+\((3, 6)\)+\((1, 4)\): \(max_w=3\), \(max_h=6\) → 18, tổng 30. Đáp án 27.

Subtask