题目描述

有 $n$ 幅画，其中第 $n$ 幅画的高为 $h_i$，宽为 $w_i$。现需要将全部的画装入若干箱子里，每个箱子可以装任意多幅画，箱子数量也可以任意多。

每个箱子的尺寸是定制的，一个箱子的长就是这个箱子中最长油画的长，宽就是这个箱子中最宽油画的宽。每个箱子的表面积为该箱子的长乘以该箱子的宽。

每幅画在装入箱子的时候，不能将长宽颠倒。请设计一种打包方案，使得所有箱子的总表面积之和最小。

输入格式

• 第一行：单个整数：表示 $n$
• 第二行到第 $n+1$ 行：第 $i+1$ 行的两个整数 $h_i$ 与 $w_i$ ，表示第 $i$ 幅画的长与宽。

输出格式

• 单个整数表示所有箱子的总表面积之和的最小值。

4
1 10
3 2
2 3
10 1

29

样例解释 1

10 + 10 + 3*3

数据范围

• $30\%$ 的数据，$1\leq n\leq 10$
• $60\%$ 的数据，$1\leq n\leq 5000$
• $100\%$ 的数据，$1\leq n\leq 300,000$
• $1\leq h_i,w_i\leq 10^9$