問題文

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

制約

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

入力

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

N K
A1 B1
A2 B2
… …
AN BN

出力

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

入出力例

2 3
1 3
2 1

6

まず、$1$ 番目のお菓子を購入します。
$1$ 番目のお菓子の値段は $1$ から $4$ に上昇します。
次に、$2$ 番目のお菓子を購入します。
$2$ 番目のお菓子の値段は $2$ から $3$ に上昇します。
最後に、$2$ 番目のお菓子を購入します。
$2$ 番目のお菓子の値段は $3$ から $4$ に上昇します。
必要なお金の最小値は、$1 + 2 + 3 = 6$ でこれ以上小さくすることはできません。

8 10
66 93
86 93
28 38
39 18
57 2
15 22
89 62
21 10

377