Warm-up round completed

Tasks

Show one task per page / all tasks on one page

"E" Parallelepiped
Time limit 2 seconds
Memory limit 256 megabytes

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.

Input format

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 format

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.

Examples
Input data
6
3 6
6 9
9 3
6 3
3 9
9 6
Output data
162
Input data
6
1 1
1 1
1 1
1 1
1 1
1 1
Output data
1
Input data
6
1 2
2 3
3 4
4 5
5 6
6 1
Output data
-1
 

Send solution

Upload Maximal size is 256kb

Log in

VK Facebook

Forgot password?

Registration

The instruction for password recovery
has been sent to your email