Problem Statement

Hearing 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.

Constraints

• All values in input are integers.
• $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$

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

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