AT_abc258_d [ABC258D] Trophy

[problemUrl]: https://atcoder.jp/contests/abc258/tasks/abc258_d $ N $ 個のステージからなるゲームがあり、$ i\ \,\ (1\ \leq\ i\ \leq\ N) $ 番目のステージは $ A_i $ 分間のストーリー映像と $ B_i $ 分間のゲームプレイによって構成されます。 初めて $ i $ 番目のステージをクリアするためにはストーリー映像の視聴とゲームプレイを両方行う必要がありますが、二回目以降はストーリー映像をスキップすることができるので、ゲームプレイのみでクリアすることができます。 初めから遊べるのは $ 1 $ 番目のステージのみですが、$ i\ \,\ (1\ \leq\ i\ \leq\ N\ -\ 1) $ 番目のステージをクリアすることにより、$ i+1 $ 番目のステージも遊べるようになります。 合計 $ X $ 回ステージをクリアするために必要な時間の最小値を求めてください。ただし、同じステージを複数回クリアしたとしても、全てクリア回数に数えられます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_N $ $ B_N $

答えを出力せよ。

### 制約 - $ 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 $ - 入力は全て整数 ### Sample Explanation 1 例えば、次のようにして $ 18 $ 分で $ 4 $ 回クリアすることができます。 - ステージ $ 1 $ をクリアする。$ A_1\ +\ B_1\ =\ 7 $ 分かかる。 - ステージ $ 2 $ をクリアする。$ A_2\ +\ B_2\ =\ 5 $ 分かかる。 - ステージ $ 2 $ を再びクリアする。$ B_2\ =\ 3 $ 分かかる。 - ステージ $ 2 $ を再びクリアする。$ B_2\ =\ 3 $ 分かかる。 $ 17 $ 分以内に $ 4 $ 回クリアすることはできません。