수조 만들기 3s 1024MB

문제

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

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

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

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

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

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

3keyboard_return
4space_bar 3keyboard_return
2space_bar 6keyboard_return
5space_bar 1

2019 KAIST RUN Spring

로그인해야 코드를 작성할 수 있어요.