题目描述

农夫$\red{John}$准备扩大他的农场,他正在考虑$\red{N (1 <= N <= 50,000) }$块长方形的土地. 每块土地的长宽满足$\red{(1 <= }$宽 $\red{<= 1,000,000}$; $\red{1 <= }$长 $\red{<= 1,000,000). }$

每块土地的价格是它的面积,但$\red{FJ}$可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换.

如果$\red{FJ}$买一块$\red{3×}$$\red{5}$的地和一块$\red{5×}$$\red{3}$的地,则他需要付$\red{5×}$$\red{5=25. }$

$\red{FJ}$希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.

输入格式

第$\red{1}$行: 一个数: $\red{N}$

第$\red{2..N+1}$行: 第$\red{i+1}$行包含两个数,分别为第$\red{i}$块土地的长和宽

输出格式

第一行: 最小的可行费用.

样例

输入样例

4
100 1
15 15
20 5
1 100

输出样例

500

提示

$\red{FJ}$分$\red{3}$组买这些土地:

第一组:$\red{100×1, }$第二组$\red{1×100, }$第三组$\red{20×5 }$和 $\red{15×5. }$

每组的价格分别为$\red{100,100,300, }$总共$\red{500.}$