配点 : $400$ 点

問題文

$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$

出力

答えを出力せよ。

3 4
3 4
2 3
4 2

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$ 回クリアすることはできません。

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

1000000076