- Final
- Elimination
- Third qual
- Second qual
- First qual
- Warm-up
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 |
|
|
|