16248번 - Parallelepiped 다국어

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 a_i times b_i 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: a_i, b_i — size of the i-th metal sheet (1 ≤ a_i, b_i ≤ 10⁶).

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.