题目描述

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

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

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

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

输入格式

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

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

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

题目大意

听到能量饮料在这些地点的评级提高，高桥决定购买 $M$ 罐能量饮料。

有 $N$ 家商店出售能量饮料。在第 $i$ 家商店中，他最多可以以 $A_i$ 日元（日本货币）购买 $B_i$ 罐能量饮料。

他可以购买 $M$ 罐能量饮料的最低金额是多少？

在给定的投入下，可以保证有足够的钱来购买 $M$ 罐能量饮料。

2 5
4 9
2 4

12

4 30
6 18
2 5
3 10
7 9

130

1 100000
1000000000 100000

100000000000000

提示

制約

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

Sample Explanation 1

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

Sample Explanation 3

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