Тюрьма для Зедда

시간 제한2초메모리 제한1024 MB

요약

n개의 직사각형 중 6개를 골라 직육면체의 여섯 면을 이루도록 배치할 때 부피가 최대가 되는 값을 구하고, 불가능하면 -1을 출력한다.

난이도: 보통10점 중 6점
유형: 해시맵, 정렬, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

Черный рейнджер нашел в жерле заброшенного вулкана $n$ прямоугольных листов металла разного размера, $i$ -й лист имеет размер $a\_i$ на $b\_i$ метров.

Зордон поручил построить Черному рейнджеру тюрьму для злобного генерала Зедда, и эта находка оказалась для него просто подарком судьбы. Тюрьма должна иметь вид прямоугольного параллелепипеда каждая грань которого представляет собой цельный лист металла. Так что рейнджер собирается взять 6 из найденных им листов металла, сложить из них параллелепипед, и показать его Зордону. Листы нельзя гнуть или разрезать, листы, из которых будет сложена тюрьма не должны выступать за её края.

Поскольку чем больше тюрьма, чем надежнее, параллелепипед должен иметь максимальный возможный объем. Помогите герою выбрать 6 листов прямоугольников так, чтобы собрать из них самую большую тюрьму.

Листы можно поворачивать, таким образом, например, листы 4 на 7 метров и 7 на 4 метра считаются одинаковыми.

입력

В первой строке дано одно число $n$ --- количество листов металла у Черного Рейнджера ( $6 \le n \le 200\\,000$ ).

В следующих $n$ строках даны пары чисел $a\_i, b\_i$ --- размеры $i$ -го куска металла ( $1 \le a\_i, b\_i \le 10^6$ ).

출력

Выведите одно целое число --- максимальный объем прямоугольного параллелепипеда, который можно собрать из этих кусков металла.

Если из данных листов невозможно собрать прямоугольный параллелепипед, выведите -1.

예제3

예제 1
입력
```
6
3 6
6 9
9 3
6 3
3 9
9 6
```
예상 출력
```
162
```
예제 2
입력
```
6
1 1
1 1
1 1
1 1
1 1
1 1
```
예상 출력
```
1
```
예제 3
입력
```
6
1 2
2 3
3 4
4 5
5 6
6 1
```
예상 출력
```
-1
```