达夫对肉上瘾了!马雷克想让她开心n天。为了在第 i 天快乐,她需要吃 ai 公斤肉。
住宅区有一家大商店,马利克想从那里给她买肉。在第 i 天,他们以每公斤 pi 美元的价格出售肉。 Malek 知道所有数字 a1, ..., an 和 p1, ..., pn。每天,他可以购买任意数量的肉,也可以保留一些肉以备将来使用。
马利克煮肉有点累了,所以他请求你帮忙。帮助他尽量减少让达夫开心 n 天所花费的总钱。
输入
输入的第一行包含整数 n (1 ≤ n ≤ 105),即天数。
接下来的 n 行中,第 i 行包含两个整数 ai 和 pi (1 ≤ ai, pi ≤ 100),即达夫当天需要的肉量和肉的成本。
输出
在一行中打印出让 Duff 开心 n 天所需的最低金额。
示例
输入 #1
3 1 3 2 2 3 1
输出 #1
10
输入 #2
3 1 3 2 1 3 2
输出 #2
8
注意
在第一个示例案例中:最佳方式是第一天购买 1 公斤,第二天购买 2 公斤,第三天购买 3 公斤。
在第二个示例案例中:最佳方式是第一天购买 1 公斤,第二天购买 5 公斤(第二天和第三天需要肉)。