Zedd를 위한 감옥

시간 제한2초메모리 제한1024 MB

요약

주어진 직사각형 판 중 6장을 골라 상자의 면 세 쌍을 만들고, 만들 수 있는 가장 큰 부피를 구합니다. 만들 수 없으면 -1을 출력합니다.

난이도: 보통10점 중 7점
유형: 그래프, 정렬, 해시맵
정답자: 아직 제출이 없습니다

문제

검은 레인저가 버려진 화산의 분화구에서 크기가 서로 다른 직사각형 금속 판 $n$ 장을 찾았다. $i$ 번째 판의 크기는 $a_i$ 미터 곱하기 $b_i$ 미터이다.

Zordon은 검은 레인저에게 악당 장군 Zedd를 가둘 감옥을 지으라고 맡겼다. 감옥은 직육면체 모양이며, 각 면은 금속 판 한 장으로 이루어진다. 레인저는 판 6장을 골라 직육면체를 조립해 Zordon에게 보여줄 것이다. 판은 구부리거나 자를 수 없고, 감옥에 쓰는 판은 직육면체의 모서리 밖으로 튀어나오면 안 된다.

감옥은 클수록 튼튼하므로, 직육면체의 부피는 가능한 한 커야 한다. 이 판들로 조립할 수 있는 직육면체의 최대 부피를 구하라.

판을 회전할 수 있다. 예를 들어 4 by 7 판과 7 by 4 판은 같은 것으로 본다.

입력

첫 줄에 금속 판의 개수 $n$ 이 주어진다 ( $6 \le n \le 200000$ ).

이어지는 $n$ 개의 줄에는 $i$ 번째 판의 크기를 나타내는 두 정수 $a_i$ 와 $b_i$ 가 주어진다 ( $1 \le a_i, b_i \le 10^6$ ).

출력

이 판들로 조립할 수 있는 직육면체의 최대 부피를 정수 하나로 출력한다.

직육면체를 조립할 수 없으면 $-1$ 을 출력한다.

예제3

예제 1
입력
```
6
3 6
6 9
9 3
6 3
3 9
9 6
```
예상 출력
```
162
```
예제 2
입력
```
6
1 1
1 1
1 1
1 1
1 1
1 1
```
예상 출력
```
1
```
예제 3
입력
```
6
1 2
2 3
3 4
4 5
5 6
6 1
```
예상 출력
```
-1
```