题目描述

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

输出格式

答えを出力せよ。

题目大意

有一款游戏，共有 $N$ 个关卡。最开始只有第 $1$ 个关卡是解锁的。在第 $i$ 个关卡过关之后，才能解锁第 $i+1$ 个关卡，每关由一部持续 $A$ 分钟的过场动画和持续 $B$ 分钟的游戏组成。

解锁的关卡可以反复再过关。第一次过关第 $i$ 个关卡时，必须观看过场动画并通关。对于第二次及以后过第 $i$ 个关卡，可以跳过过场动画，直接进行游戏。

找出通关 $X$ 次所需的最短时间。（ $X$ 次中可以是已通过的关卡再次通关。）

3 4
3 4
2 3
4 2

18

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

1000000076

提示

制約

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