配点 : 300 点

問題文

栄養ドリンクにレーティング上昇効果があると聞いた高橋くんは、$M$ 本の栄養ドリンクを買い集めることにしました。

栄養ドリンクが売られている店は $N$ 軒あり、$i$ 軒目の店では $1$ 本 $A_i$ 円の栄養ドリンクを $B_i$ 本まで買うことができます。

最小で何円あれば $M$ 本の栄養ドリンクを買い集めることができるでしょうか。

なお、与えられる入力では、十分なお金があれば $M$ 本の栄養ドリンクを買い集められることが保証されます。

制約

• 入力は全て整数である。
• $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$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

出力

$M$ 本の栄養ドリンクを買い集めるのに必要な最小の金額を出力せよ。

2 5
4 9
2 4

12

$12$ 円あれば $1$ 軒目の店で $1$ 本、$2$ 軒目の店で $4$ 本の栄養ドリンクを購入し、合計 $5$ 本の栄養ドリンクを買い集めることができます。一方、$11$ 円以下では $5$ 本の栄養ドリンクを買い集めることができません。

4 30
6 18
2 5
3 10
7 9

130

1 100000
1000000000 100000

100000000000000

出力が $32$ ビット整数型におさまらないことがあります。