题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

4
100 1
15 15
20 5
1 100

输出样例

500

提示

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

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

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