Energy Drink Collector

题目描述

听说能量饮料会提高那些网站的评分，高桥决定购买 $M$ 罐能量饮料。 有 $N$ 家商店出售能量饮料。在第 $i$ 家商店，他最多可以以每罐 $A_i$ 日元的价格购买 $B_i$ 罐能量饮料。 买到 $M$ 罐能量饮料所需的最少金额是多少？ 保证在给定输入下，总能用足够的金额买到 $M$ 罐能量饮料。

输入格式

输入以标准输入给出，格式如下： $N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

输出高桥购买 $M$ 罐能量饮料所需的最少金额。

2 5
4 9
2 4

12

4 30
6 18
2 5
3 10
7 9

130

1 100000
1000000000 100000

100000000000000

提示

输入中的所有数值都是整数。 $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$花费 $12$ 日元时，我们可以在第一家店买一罐，在第二家店买四罐，总共五罐。然而，无法用 $11$ 日元或更少买到 $5$ 罐。
输出可能无法装入 32 位整数类型。

标签: AtCoder|abc121C

来源

AtCoder|abc121C