C - 能量饮料收集者

得分: 300 分

问题描述

听说能量饮料能够提高评分，在这个网站，高桥决定买 $M$ 罐能量饮料。

有 $N$ 家商店出售能量饮料。在第 $i$ 家商店，他可以以每罐 $A_i$ 日元的价格买到最多 $B_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$ 罐能量饮料所需的最少金额。

2 5
4 9
2 4

12

用 12 日元，我们可以在第一家商店买一罐，在第二家商店买四罐，总共买到了五罐。然而，在 11 日元或更少的金额中，我们无法买到 5 罐。

4 30
6 18
2 5
3 10
7 9

130

1 100000
1000000000 100000

100000000000000

输出结果可能不适合 $32$ 位整数类型。