평행육면체
시간 제한2초메모리 제한512 MB
n장의 직사각형 판 중 6장을 골라 직육면체의 면을 만들 때, 마주 보는 면의 크기가 같아야 한다. 만들 수 있는 직육면체의 최대 부피를 구하고, 불가능하면 -1을 출력한다.
문제
Black Ranger는 직육면체를 만들려고 한다. 그러려면 가지고 있는 n장의 직사각형 금속판 중 6장을 사용할 계획이다. i번째 금속판의 크기는 ai 곱하기 bi 미터이다.
직육면체의 각 면은 금속판 하나로 이루어져야 한다. 금속판은 구부리거나 자를 수 없고, 직육면체의 경계를 벗어나서도 안 된다. 필요하면 금속판을 회전해도 된다.
Black Ranger는 부피가 최대가 되는 직육면체를 만들려고 한다. 그를 도와주자.
입력
첫째 줄에 금속판의 수 n이 주어진다 (6 ≤ n ≤ 200 000).
다음 n개 줄에 두 정수 쌍 ai, bi가 주어진다. 이는 i번째 금속판의 크기이다 (1 ≤ ai, bi ≤ 106).
출력
주어진 금속판으로 만들 수 있는 직육면체 부피의 최댓값을 정수 하나로 출력한다. 직육면체를 만들 수 없다면 -1을 출력한다.