Abc 121 C - Energy Drink Collector

Problem StatementHearing that energy drinks increase rating in those sites, Takahashi decides to buy up M cans of energy drinks.

There are N stores that sell energy drinks.

In the i-th store, he can buy at most B i  cans of energy drinks for A i  yen (the currency of Japan) each.

What is the minimum amount of money with which he can buy M cans of energy drinks?

It is guaranteed that, in the given inputs, a sufficient amount of money can always buy M cans of energy drinks.

ConstraintsAll values in input are integers.

1≤N,M≤10 5 1≤A i ≤10 9 1≤B i ≤10 5 B 1 +...+B N ≥M

Input

Input is given from Standard Input in the following format:N MA 1  B 1 A 2  B 2 ⋮A N  B N

Output

Print the minimum amount of money with which Takahashi can buy M cans of energy drinks.Sample

Input

2 54 92 4

Sample Output 12

With 12 yen, we can buy one drink at the first store and four drinks at the second store, for the total of five drinks.

 However, we cannot buy 5 drinks with 11 yen or less.

---------

数组排序, 按照最少的价格去买饮料,但是数据范围很大, 用二维数组会溢出,所以就用hashmap里面的treemap,自带排序那种来处理.