問題文

$N$ 個のステージからなるゲームがあり、$i \\, (1 \\leq i \\leq N)$ 番目のステージは $A_i$ 分間のストーリー映像と $B_i$ 分間のゲームプレイによって構成されます。

初めて $i$ 番目のステージをクリアするためにはストーリー映像の視聴とゲームプレイを両方行う必要がありますが、二回目以降はストーリー映像をスキップすることができるので、ゲームプレイのみでクリアすることができます。

初めから遊べるのは $1$ 番目のステージのみですが、$i \\, (1 \\leq i \\leq N - 1)$ 番目のステージをクリアすることにより、$i+1$ 番目のステージも遊べるようになります。

合計 $X$ 回ステージをクリアするために必要な時間の最小値を求めてください。ただし、同じステージを複数回クリアしたとしても、全てクリア回数に数えられます。

制約

• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq A_i, B_i \\leq 10^9 \\, (1 \\leq i \\leq N)$
• $1 \\leq X \\leq 10^9$
• 入力は全て整数

入力

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

$N$ $X$ $A_1$ $B_1$ $\\vdots$ $A_N$ $B_N$

出力

答えを出力せよ。

入力例 1

3 4
3 4
2 3
4 2

出力例 1

18

例えば、次のようにして $18$ 分で $4$ 回クリアすることができます。

• ステージ $1$ をクリアする。$A_1 + B_1 = 7$ 分かかる。
• ステージ $2$ をクリアする。$A_2 + B_2 = 5$ 分かかる。
• ステージ $2$ を再びクリアする。$B_2 = 3$ 分かかる。
• ステージ $2$ を再びクリアする。$B_2 = 3$ 分かかる。

$17$ 分以内に $4$ 回クリアすることはできません。

入力例 2

10 1000000000
3 3
1 6
4 7
1 8
5 7
9 9
2 4
6 4
5 1
3 1

出力例 2

1000000076