33520번 - 초코바 만들기

문제

형진이는 친구들에게 나누어 줄 $N$개의 초코바를 직접 만들기로 했다. 모든 초코바는 직육면체 모양으로, 높이(두께)는 동일하지만 바닥 면의 가로와 세로 길이만 각각 다르다. 구체적으로 $i$번째 초코바의 바닥 면의 가로 길이는 $a_i$이고, 세로 길이는 $b_i$이다.

초코바를 만들기 위해서는 틀에 넣어 굳혀야 한다. $(a_i, b_i)$ 크기의 초코바를 틀에 넣을 때, 초코바를 90도 회전시켜 $(b_i, a_i)$ 형태로 놓을 수도 있다. 이때, 틀의 크기를 $(W, H)$라고 할 때, $i$번째 초코바가 이 틀에 들어가려면 다음 두 조건 중 하나를 만족해야 한다.

• $a_i \leq W$ 이고 $b_i \leq H$
• $b_i \leq W$ 이고 $a_i \leq H$

즉, 초코바를 회전시키지 않은 상태이거나 90ドル^{\circ}$회전시킨 상태 중 하나로 틀의 가로와 세로 크기에 맞게 넣을 수 있으면 된다.

형진이는 $N$개의 초코바를 모두 굳힐 수 있는 최소 면적의 직사각형 틀을 찾고자 한다. 이때, 그 틀의 최소 면적을 출력하시오.

입력

첫 번째 줄에 초코바의 개수 $N$이 주어진다. $(1 \le N \le 200,000円)$

이후 $N$개의 줄에 걸쳐, 각 초코바의 길이 정보가 주어진다.

$N$개의 줄 중 $i$번째 줄에는, $i$번째 초코바의 가로 길이를 나타내는 정수 $a_i$와 세로 길이를 나타내는 정수 $b_i$가 주어진다. $(1 \le a_i, b_i \le 10^9)$

출력

모든 초코바를 굳힐 수 있는 틀의 최소 면적을 출력한다.

제한

힌트