题目描述

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

有 $N$ 家商店出售能量饮料。在第$i$家商店，他可以以每罐 $A_i$日元的价格买到最多 $B_i$ 罐能量饮料。

他最少需要花多少钱才能买到 $M$ 罐能量饮料?

保证在给定的输入中，总有足够的钱买到$M$罐能量饮料。

输入

输入第一行$N,M$两个整数

接下来一共$N$行，表示第$i$家商店的饮料的$A_i$和$B_i$

输出

输出高桥买$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位整数类型。

$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 \ge M$