大样例下载

题目描述

小明准备购买一些矩形木板，为此他来到了一家木材商店。

有意思的是，这家商店的木板是按面积来定价的，也就是说，一块木板的价格恰好等于它的面积。

可是最近木板销量不好，为此老板推出了促销活动：顾客可以选择任意若干块木板打包购买，总价为该包木板中最大的长度乘以最大的宽度。

经过挑选，小明准备买下其中的 $N$ 块矩形木板。他发现，如果将这些木板分批次打包购买，可能可以节省支出。他想知道他最少需要花费多少钱。

自然地，这个问题交给了你。给出这 $N$ 块木板的长度和宽度，请你计算并输出小明买下这些木板所需的最少花费。

输入格式

第一行：一个整数 $N$

接下来 $N$ 行，每行两个整数 $L_i$ 和 $W_i$，分别表示第 $i$ 块木板的长度和宽度。

输出格式

一行，一个整数，表示最少花费

样例输入

4 
3 5
10 1
5 3
1 10

样例输出

45

样例解释

分三个批次购买：

• 第一批次：单独购买第 2 块木板，花费 $10 × 1=10$；
• 第二批次：打包购买第 1，3 块木板，花费 $5 × 5=25$；
• 第三批次：单独购买第 4 块木板，花费 $1 × 10=10$；

总花费为 $10 + 25 + 10 = 45$。除此之外，你找不到花费更少的购买方式。

数据范围

20% 的数据：$1 ≤ N ≤ 10$

40% 的数据：$1 ≤ N ≤ 100$

50% 的数据：$1 ≤ N ≤ 1000$

100% 的数据：$1 ≤ N ≤ 5 × 10^4$，$1 ≤ L_i, W_i ≤ 10^6$。