题目描述

听说能量饮料在这些网站上的评分提高了，高桥决定买 $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$ 罐能量饮料。

示例输入 1

2 5
4 9
2 4

示例输出 1

12

用 12 日元，我们可以在第一家商店买一罐饮料，在第二家商店买四罐饮料，总共五罐。然而，我们不能用 11 日元或更少的钱买到 5 罐饮料。

示例输入 2

4 30
6 18
2 5
3 10
7 9

示例输出 2

130

示例输入 3

1 100000
1000000000 100000

示例输出 3

100000000000000

输出可能无法适应 32 位整数类型。