The black ranger found n rectangular sheets of metal of different sizes in the mouth of an abandoned volcano, the i-th sheet has the size a
i by b
i meters.
Zordon instructed the Black Ranger to build a prison for the evil General Zedd, and this find turned out to be just a gift of fate for him. The prison should look like a rectangular parallelepiped, each face of which is a solid sheet of metal. So the ranger is going to take 6 of the sheets of metal he found, fold them into a box, and show it to Zordon. The sheets must not be bent or cut, the sheets from which the prison will be folded must not protrude beyond its edges.
Since the larger the prison, the more reliable, the box should have the maximum possible volume. Help the hero choose 6 sheets of rectangles so as to make the biggest prison out of them.
Sheets can be rotated, so, for example, sheets 4 by 7 meters and 7 by 4 meters are considered the same.
Input data format
The first line contains a single number n — the number of metal sheets the Black Ranger has (6 ≤ n ≤ 200,000).
The next n lines contain pairs of numbers a
i; b
i — dimensions of the i-th piece of metal (1 ≤ a
i; b
i ≤ 10
6).
Output data format
Print a single integer — the maximum volume of a cuboid that can be assembled from these pieces of metal.
If it is impossible to assemble a rectangular parallelepiped from the given sheets, print -1.
Examples
| # |
Input |
Output |
| 1 |
6
36
6 9
9 3
6 3
39
96 |
162 |
| 2 |
6
1 1
1 1
1 1
1 1
1 1
1 1
| 1 |
| 3 |
6
1 2
23
34
4 5
5 6
6 1
| -1 |