分数: 300 点
问题陈述
听说能量饮料在这些网站上的评分提高,高桥决定购买 M 罐装能量饮料。
有 N 销售能量饮料的商店。在 i第第商店,他最多可以购买 B_i 罐装能量饮料 A_i 日元(日本货币)各一个。
他可以购买的最低金额是多少 M 罐装能量饮料?
保证在给定的投入下,总能买到足够多的钱 M 罐装能量饮料。
约束
- 输入中的所有值都是整数。
- 1 \leq N, M \leq 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^5
- B_1 + ... + B_N \geq M
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 \vdots A_N B_N
输出
打印高桥可以购买的最低金额 M 罐装能量饮料。
示例输入 1
2 5 4 9 2 4
示例输出 1
12
与 12 日元,我们可以在第一家商店购买一杯饮料,在第二家商店购买四杯饮料,总共五杯饮料。然而我们买不到 5 饮料 11 日元或更少。
示例输入 2
4 30 6 18 2 5 3 10 7 9
示例输出 2
130
示例输入 3
1 100000 1000000000 100000
示例输出 3
100000000000000
输出可能不适合 32位整数类型。