Phân nhóm

Xem dạng PDF
Gửi bài giải
Điểm: 0,78 (OI)
Giới hạn thời gian: 0.7s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
USACO MAR08
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho ~n \leq 300000~ cặp số ~(x, y)~ ~(1 \leq x, y \leq 1000000)~. Ta có thể nhóm một vài cặp số lại thành một nhóm. Giả sử một nhóm gồm các cặp số thứ ~a_1, a_2, \dots, a_m~ thì chi phí cho nhóm này sẽ là ~\max(x_{a_1}, x_{a_2}, \dots, x_{a_m}) \times \max(y_{a_1}, y_{a_2}, \dots, y_{a_m})~.

Yêu cầu: tìm cách phân nhóm có tổng chi phí bé nhất.

Input

  • Dòng đầu tiên là số nguyên dương ~N~.
  • ~N~ dòng tiếp theo dòng thứ ~i~ ghi ~2~ số ~x_i~ và ~y_i~.

Output

Gồm 1 số duy nhất là kết quả tìm được.

Sample Input

4
100 1
15 15
20 5
1 100

Sample Output

500

Note

Có 3 nhóm lần lượt là (1), (2,3) và (4).

Bình luận

Hãy đọc nội quy trước khi bình luận.