문제
농부 창호는 지금 자신의 눈앞에 펼쳐진 N(1≤N≤50,000)개의 땅을 사고자 한다.
각각의 땅은 사각형의 모양새를 띄고 있고, 정수 범위의 가로와 세로로 이루어져 있다. 가로와 세로는 서로 바뀔 수 없다.
농부 창호가 한 개의 땅을 사게 되면, (가로)×(세로)만큼의 비용을 지불해야 하는데,
한 번에 여러 개의 땅을 사게 되면 (땅들의 가로 중 최댓값)×(땅들의 세로 중 최댓값)만큼의 비용을 지불하면 된다.
예를 들어 창호가 15×15의 땅과, 5×20의 땅을 샀을 경우엔 각각 225, 100의 비용이 필요하기 때문에 총 325의 비용을 지불하는데,
15×15의 땅과 5×20의 땅을 한 번에 살 경우 15×20=300의 비용만을 지불 하면 된다.
창호는 모든 땅을 사고자 하는데, 한 번에 모든 땅을 사는 것이 아닌, 여러 번에 걸쳐 땅을 사려고 한다.
이 때 창호가 지불해야 하는 비용을 최소화 하는 프로그램을 작성하라.
입력
첫 번째 줄에는 창호가 살 수 있는 땅의 개수 N(1≤N≤50,000)이 입력된다. 그 다음 줄부터는 N개의 땅의 가로와 세로가 공백을 사이에 두고 한 줄에 하나씩 입력된다.
가로와 세로의 범위는 1이상 1,000,000이하이다.
출력
창호가 모든 땅을 살 때 내게 되는 최소의 비용을 출력한다.
예제1
입력
4
1001
1515
205
1100
출력
500
힌트
출처
USACO 2008 Mar Gold 1