Prison for Zedd

Time limit2sMemory limit1024 MB

Summary

Pick six of the given rectangles to form the three face pairs of a box and report the largest possible volume, or -1 if no box can be built.

Level: Medium7 of 10
Topics: Graph, Sorting, Hash map
Solved: No attempts yet

Statement

The Black Ranger found $n$ rectangular metal sheets of different sizes in the crater of an abandoned volcano. Sheet $i$ measures $a_i$ meters by $b_i$ meters.

Zordon asked the Black Ranger to build a prison for the evil general Zedd, and these sheets are a lucky find. The prison must be a rectangular box where each face is one whole sheet. The Ranger will take 6 of the sheets, assemble the box, and show it to Zordon. Sheets cannot be bent or cut, and no sheet used in the prison may stick out past the edges of the box.

A bigger prison is a safer prison, so the box must have the largest possible volume. Find the maximum volume of a box that can be assembled from these sheets.

Sheets may be rotated. For example, a 4 by 7 sheet and a 7 by 4 sheet are considered the same.

Input

The first line contains one integer $n$ , the number of metal sheets ( $6 \le n \le 200000$ ).

Each of the next $n$ lines contains two integers $a_i$ and $b_i$ , the dimensions of the $i$ -th sheet ( $1 \le a_i, b_i \le 10^6$ ).

Output

Print one integer, the maximum volume of a rectangular box that can be assembled from these sheets.

If no box can be assembled, print $-1$ .

Examples3

Example 1
Input
```
6
3 6
6 9
9 3
6 3
3 9
9 6
```
Expected output
```
162
```
Example 2
Input
```
6
1 1
1 1
1 1
1 1
1 1
1 1
```
Expected output
```
1
```
Example 3
Input
```
6
1 2
2 3
3 4
4 5
5 6
6 1
```
Expected output
```
-1
```