您可能已经知道,空间一直是 ICPC 雅加达的一个问题。为了应对这一问题,ICPC 雅加达计划建造两座新大楼。这些建筑物的形状应为相同大小的矩形。现在,他们的问题是找到土地来建造建筑物。
有 $$$N$$$ 土地可供出售。 $$$i^{th}$$$ 土地呈矩形,大小为 $$$L_i \times W_i$$$。为了获得良好的风水,建筑物的侧面应与土地的侧面平行。
一种方法是在两块不同的土地上建造两座建筑物,每块土地上建造一座(不一定具有相同的方向)。当且仅当至少满足以下条件之一时,才能在 $$$i^{th}$$$ 土地上建造规模为 $$$A \times B$$$ 的建筑物:
- $$$A \le L_i$$$ 和 $$$B \le W_i$$$,或
- $$$A \le W_i$$$ 和 $$$B \le L_i$$$。
- $$$A \times 2 \le L_i$$$ 和 $$$B \le W_i$$$,或
- $$$A \times 2 \le W_i$$$ 和 $$$B \le L_i$$$,或
- $$$A \le L_i$$$ 和 $$$B \times 2 \le W_i$$$,或
- $$$A \le W_i$$$ 和 $$$B \times 2 \le L_i$$$。
您在此问题中的任务是帮助 ICPC Jakarta 找出在 $$$N$$$ 可用土地上他们可以建造的最大建筑物。请注意,ICPC 雅加达必须建造两栋 $$$A \times B$$$ 的建筑物;输出 $$$A \times B$$$ 的最大可能值。
输入
输入以包含整数的行开头: $$$N$$$ ($$$1 \le N \le 100\,000$$$) 表示可用土地的数量。接下来的 $$$N$$$ 行每行包含两个整数: $$$L_i$$$ $$$W_i$$$ ($$$1 \le L_i, W_i \le 10^9$$$) 表示土地的大小。
输出
在一行中输出一个数字,代表 ICPC Jakarta 可以建造的最大建筑物,精确到一位小数(为清楚起见,请参阅示例输入/输出)。
示例
输入 #1
2 5 5 3 4
输出 #1
12.5
输入 #2
2 2 5 4 3
输出 #2
8.0
输入 #3
3 10 1 9 8 7 6
输出 #3
42.0
注意
示例输入/输出 #1 的说明
在第一块土地上可以建造两栋 $$$2.5 \times 5$$$ 的建筑物。
示例输入/输出#2 的说明
在第一块土地和第二块土地上可以分别建造两栋 $$$2 \times 4$$$ 的建筑物。
示例输入/输出 #3 的说明
在第二块和第三块土地上可以分别建造两栋 $$$7 \times 6$$$ 的建筑物。