题目描述

听到能量饮料在这些地点的评级提高，高桥决定购买 $M$ 罐能量饮料。

有 $N$ 家商店出售能量饮料。在第 $i$ 家商店中，他最多可以以 $A_i$ 日元（日本货币）购买 $B_i$ 罐能量饮料。

他可以购买 $M$ 罐能量饮料的最低金额是多少？

在给定的投入下，可以保证有足够的钱来购买 $M$ 罐能量饮料。

输入格式

第一行两个正整数 $N, M$，$1 \le N, M \le 10^5$。

接下来 $N$ 行，每行两个正整数 $A_i, B_i$，$1 \le A_i \le 10^9$，$1 \le B_i \le 10^5$，$B_1 + B_2 + ... + B_N \ge M$。

输出格式

购买 $M$ 罐能量饮料的最低金额。

2 5
4 9
2 4

12

4 30
6 18
2 5
3 10
7 9

130

1 100000
1000000000 100000

100000000000000