← 返回题目列表

Codeforces · 588/A

A. 达夫和肉

中文机器翻译题面 查看原题

达夫对肉上瘾了!马雷克想让她开心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 公斤(第二天和第三天需要肉)。