Page not loading? Try clicking here.
Placeholder

#6241

수조 만들기 3s 1024MB

Problems

정올이는 총 N개의 직사각형 모양의 벽돌로 수조를 만들고자 한다. 주어진 직사각형은 자유롭게 회전(90도)할 수 있으며, 직사각형의 배열도 자유롭게 할 수 있다.

위는 임의로 만든 수조의 예시이다. 수조에 최대로 물을 채웠을 때의 상황을 나타내었다.

총 N개의 직사각형 벽돌의 크기가 주어졌을 때, 만들 수 있는 수조의 형태 중 채울 수 있는 물의 양의 최대값을 구해보자.


Input

첫 줄의 벽돌의 개수 N이 주어진다. (3\leq N\leq 250000)

그 다음 N줄에 걸쳐 벽돌의 크기에 대한 정보 (h_i, w_i)가 공백으로 구분되어 주어진다. (1\leq h_i, w_i\leq 10^6)


Output

만들 수 있는 수조의 형태 중 채울 수 있는 물의 양의 최대값을 한 줄에 출력하여라.


Example 

3
4 3
2 6
5 1
15

Source

2019 KAIST RUN Spring
You must sign in to write code.