Задача №114984. Тюрьма для Зедда
Черный рейнджер нашел в жерле заброшенного вулкана n прямоугольных листов металла разного размера, i -й лист имеет размер a i на b i метров.
Зордон поручил построить Черному рейнджеру тюрьму для злобного генерала Зедда, и эта находка оказалась для него просто подарком судьбы. Тюрьма должна иметь вид прямоугольного параллелепипеда каждая грань которого представляет собой цельный лист металла. Так что рейнджер собирается взять 6 из найденных им листов металла, сложить из них параллелепипед, и показать его Зордону. Листы нельзя гнуть или разрезать, листы, из которых будет сложена тюрьма не должны выступать за её края.
Поскольку чем больше тюрьма, чем надежнее, параллелепипед должен иметь максимальный возможный объем. Помогите герою выбрать 6 листов прямоугольников так, чтобы собрать из них самую большую тюрьму.
Листы можно поворачивать, таким образом, например, листы 4 на 7 метров и 7 на 4 метра считаются одинаковыми.
В первой строке дано одно число n — количество листов металла у Черного Рейнджера ( 6 ≤ n ≤ 200 000 ).
В следующих n строках даны пары чисел a i , b i — размеры i -го куска металла ( 1 ≤ a i , b i ≤ 10 6 ).
Выведите одно целое число — максимальный объем прямоугольного параллелепипеда, который можно собрать из этих кусков металла.
Если из данных листов невозможно собрать прямоугольный параллелепипед, выведите -1 .
Первая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 500 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 27 баллов.
Вторая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 10 000 . Баллы за эту группу начисляются только при прохождении всех тестов этой и предыдущих групп. Стоимость группы составляет 36 баллов.
Третья группа тестов состоит из тестов, для которых выполняются полные ограничения. В этой подгруппе несколько тестов, каждый из которых оценивается независимо, но для тестирования третьей подгруппы решение должно пройти первые две группы. Стоимость группы составляет 37 баллов.
Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку « Запросить информацию о проверке » на вкладке « Решения ».
6 3 6 6 9 9 3 6 3 3 9 9 6
162
6 1 1 1 1 1 1 1 1 1 1 1 1
1
6 1 2 2 3 3 4 4 5 5 6 6 1
-1