能量饮料

题目描述

高桥君听说能量饮料有提升 Rating 的效果，决定买齐 $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

有 $12$ 日元时，可以在第 $1$ 家商店买 $1$ 瓶、在第 $2$ 家商店买 $4$ 瓶能量饮料，合计买齐 $5$ 瓶。另一方面，$11$ 日元以下无法买齐 $5$ 瓶。

4 30
6 18
2 5
3 10
7 9

130

1 100000
1000000000 100000

100000000000000

答案可能超出 $32$ 位整数类型的范围。

数据范围

• 输入均为整数
• $1 \le N, M \le 10^5$
• $1 \le A_i \le 10^9$
• $1 \le B_i \le 10^5$
• $B_1 + ... + B_N \ge M$