Phân nhóm

View as PDF

Submit solution


Points: 0.78 (partial)
Time limit: 0.7s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
USACO MAR08
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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).


Comments

Please read the guidelines before commenting.


There are no comments at the moment.