Snack Shop 2

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

• 入力はすべて整数である。

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

N K
A1 B1
A2 B2
… …
AN BN

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

2 3
1 3
2 1

6

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

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

377