시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Black Ranger wants to create a rectangular parallelepiped. To do it he plans to use 6 of n rectangular metal sheets he has. The i-th sheet has size ai times bi meters.

Each face of the parallelepiped must be a solid metal sheet. The sheets must not be bent or cut and must not stand out of its limits. The sheets can be rotated if necessary.

Black Ranger wants to create a parallelepiped with the maximal possible volume. Help him.

입력

The first line contains one integer n — the number of metal sheets Black Ranger has (6 ≤ n ≤ 200 000).

The following n lines contain two pairs of integers each: ai, bi — size of the i-th metal sheet (1 ≤ ai, bi ≤ 106).

출력

Output one integer — the maximal possible volume of a parallelepiped that can be created using the given metal sheets. If no parallelepiped can be created, output  - 1.

예제 입력 1

6
3 6
6 9
9 3
6 3
3 9
9 6

예제 출력 1

162

예제 입력 2

6
1 1
1 1
1 1
1 1
1 1
1 1

예제 출력 2

1

예제 입력 3

6
1 2
2 3
3 4
4 5
5 6
6 1

예제 출력 3

-1