Hearing that chocolate is good for the brain and nervous system, student Vasily decides to buy
M chocolate bars. There are
N shops in the city that sell a variety of chocolates. In the
i store, Vasily can buy no more than
Bi chocolate bars by
Ai< /sub> rubles each. Help Vasily determine the minimum amount of money he needs to save up to buy
M chocolate bars?
It is guaranteed that Vasily will always be able to buy
M chocolate bars with the required amount.
Input
The first line contains two numbers:
N and
M (1 <= N, M <= 10
5). The following
N lines contain 2 numbers each:
Ai (1 <= A
i <= 10
9) and
Bi (1 <= B
i <= 10
5 ).
\(B_1 + B_2 +... + B_N >= M\).
Imprint
Print the minimum amount of money Vasily needs to buy
M chocolate bars.
Examples
| # |
Input |
Output |
| 1 |
2 5
49
24 |
12 |
| 2 |
4 30
6 18
25
3 10
7 9
| 130 |
| 3 |
1 100000
1000000000 100000
| 100000000000000 |