[Usaco2008 Mar]土地购买

农夫 John 准备扩大农场，并计划购买 $N$ 块长方形土地。第 $i$ 块土地的长为 $L_i$，宽为 $W_i$。

每块土地可以单独购买，也可以将若干块土地分为一组同时购买。一组土地的价格等于组内所有土地的最大长度与最大宽度的乘积。土地的长和宽不能交换。例如，同时购买一块长宽为 $3\times 5$ 的土地和一块长宽为 $5\times 3$ 的土地，需要支付的费用为 $5\times 5=25$。

农夫 John 希望购买全部土地。请合理地将这些土地分组，使总费用最小。

输入格式

第一行包含一个整数 $N$，表示土地的数量。

接下来 $N$ 行，第 $i$ 行包含两个整数 $L_i$ 和 $W_i$，分别表示第 $i$ 块土地的长和宽。

输出格式

输出一个整数，表示购买全部土地所需的最小总费用。

样例输入

4
100 1
15 15
20 5
1 100

样例输出

500

数据范围

• $1\le N\le 5\times 10^4$；
• $1\le L_i\le 10^6$；
• $1\le W_i\le 10^6$。

来源与许可

本题为 USACO 2008 March 试题「土地购买」，题面与测试数据整理自 BZOJ。

样例 1

输入

4
100 1
15 15
20 5
1 100

输出

500