問題文

$N$ 種類のお菓子がたくさん販売されている店があります。
$i \: (1 ≦ i ≦ N)$ 種類目のお菓子は、初めは $A_i$ のお金を払うことによって購入することができますが、購入するたびに、購入に必要なお金が $B_i$ だけ減少します。
ただし、必要なお金が $1$ より下がることはありません。
$K$ 個のお菓子を買うために必要なお金の最小値を求めてください。

制約

• $1 \leq N \leq 10^{5}$
• $1 \leq K \leq 10^{9}$
• $1 \leq A_i, B_i \leq 10^{9}$
• 入力はすべて整数である。

入力

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

N K
A1 B1
A2 B2
… …
AN BN

出力

問題の答えを一行に出力せよ。

入出力例

3 3
5 1
7 3
8 2

12

$2$ 番目のお菓子を $3$ 個購入すると、$7 + 4 + 1 = 12$ のお金で購入できます。
また、$1$ 番目のお菓子を $3$ 個購入することでも、$5 + 4 + 3 = 12$ のお金で購入できます。

15 100
65 10
24 3
88 7
61 4
16 7
24 7
82 10
76 1
63 8
51 5
10 10
26 3
11 5
92 3
55 8

109