시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 75 17 13 29.545%

문제

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

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

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

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

입력

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

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

출력

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

예제 입력

4
100 1
15 15
20 5
1 100

예제 출력

500

힌트

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