GROUP - Phân nhóm

Giới hạn

• Thời gian: 0.661s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Cho n<=300000 cặp số (x,y) (1<=x, y<=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ứ a1, a2, ..., am thì chi phí cho nhóm này sẽ là max(x _a1 , x _a2 , ..., x _am ) * max(y _a1 , y _a2 , ..., y _am ).

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

Dữ liệu

• 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ố xi và yi.

Kết quả

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

Ví dụ

Dữ liệu:
4
100 1
15 15
20 5
1 100

Kết quả:
500

Giải thích: 
Có 3 nhóm lần lượt là (1), (2,3) và (4). 

---

• Người up: aukcwe
• Nguồn bài: USACO MAR08