쌍둥이 빌딩

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

요약

N개의 직사각형 땅이 주어질 때, 서로 다른 두 땅에 놓거나 한 땅에 두 채를 놓는 경우를 모두 고려해 두 동일 건물의 최대 넓이 A×B를 구하고 소수점 한 자리로 출력한다.

문제

아시다시피 ICPC 자카르타에서는 항상 공간이 부족했다. 이를 해결하기 위해 ICPC 자카르타는 두 개의 새 빌딩을 지으려고 한다. 두 빌딩은 같은 크기의 직사각형 모양이어야 한다. 이제 남은 문제는 빌딩을 지을 땅을 찾는 것이다.

판매 중인 땅이 N개 있다. i번째 땅은 Li × Wi 크기의 직사각형이다. 좋은 풍수를 위해 빌딩의 변은 땅의 변과 평행해야 한다.

한 가지 방법은 두 빌딩을 서로 다른 두 땅에 하나씩 짓는 것이다(방향이 같을 필요는 없다). A × B 크기의 빌딩은 다음 조건 중 하나 이상을 만족할 때에만 i번째 땅에 지을 수 있다:

또는 같은 방향으로 A × B 크기의 빌딩 두 개를 i번째 땅에 지을 수도 있다. 정확히 말해, A × B 크기의 빌딩 두 개를 i번째 땅에 지을 수 있는 것은 다음 조건 중 하나 이상을 만족할 때에만 가능하다:

이 문제에서 여러분의 임무는 N개의 땅이 주어졌을 때 ICPC 자카르타가 지을 수 있는 가장 큰 빌딩을 구하는 것이다. ICPC 자카르타는 A × B 크기의 빌딩 두 개를 지어야 하며, 가능한 A × B의 최댓값을 출력한다.

입력은 정수 N (1 ≤ N ≤ 100 000)이 있는 한 줄로 시작한다. N은 판매 중인 땅의 수이다. 다음 N개 줄에는 각각 두 정수 Li Wi (1 ≤ Li, Wi ≤ 10^9)가 주어지며, 땅의 크기를 나타낸다.

ICPC 자카르타가 지을 수 있는 가장 큰 빌딩의 크기를 소수점 한 자리까지 출력한다(명확한 형식은 입출력 예시를 참고한다).