Informatica Online Judge

  땅따먹기 [2046 / 07FE]

Time Limit(Test case) : 200(ms)
Number of users who solved : 13   Total Tried : 19


The Champion of this Problem (C++) : gs16106 - 0ms / 697byte
My Best Submission (C++) : N/A

[USACO March 2008 Gold]

Background

농부 상헌이는 선재의 부동산에서 N개의 땅을 모두 사려고 한다. 땅은 Wi * Hi 크기의 직사각형으로 생각할 수 있다.

선재는 그동안 땅 하나의 가격을 Wi * Hi로 매겨서 팔았는데, 사실 요즘 선재는 장사가 잘 안된다. 손님이 급한 선재는 다음과 같은 묶음 할인 행사를 통해서 땅을 팔고 있다.

* 여러개의 땅을 살 때는, (해당 땅 중 Wi의 최댓값) * (해당 땅 중 Hi의 최댓값) 으로 가격을 매긴다.

상헌이는 선재의 행사가 매우 좋다고 생각해서 땅을 살 준비를 하고 있었지만, 땅을 어떻게 묶어사는지에 따라 가격이 천차만별이라는 사실을 깨닫게 되었다! 상헌이가 최소 비용으로 땅을 묶어서 살 경우, 최소 비용은 얼마일까?

Input

첫번째 줄에 N이 주어진다. (1 <= N <= 50000)

이후 N개의 줄에 Wi, Hi가 주어진다. (1 <= Wi, Hi <= 1000000)

50%의 테스트 케이스에 대해서 N <= 1000을 만족한다.

Output

상헌이가 땅을 사는 최소 비용을 출력하라.

IO Example

입력1
4
100 1
15 15
20 5
1 100

출력1
500

설명
(1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]