Energy Drink Collector

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ stores. Store $i$ sells at most $B_i$ energy drinks at price $A_i$ each. Buy exactly $M$ drinks with minimum total cost.

Input

The first line contains $N,M$. Each of the next $N$ lines contains $A_i,B_i$.

Output

Print the minimum cost.

Subtasks

General constraints:

• $1 \le N,M \le 10^5$.

• $1 \le A_i \le 10^9$.

• $1 \le B_i \le 10^5$.

• $\sum B_i \ge M$.

• Subtask 1 (20 points): $N,M \le 20$, $A_i \le 100$

• Subtask 2 (30 points): $N,M \le 2000$, $A_i \le 10^6$

• Subtask 3 (50 points): No additional constraints.

Examples

Input

2 5
4 9
2 4

Output

12

Explanation

Buy four drinks at price $2$ and one at price $4$. The total cost is $4\cdot2+1\cdot4=12$.