D - Trophy Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ。

入力例 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

Score : 400 points

Problem Statement

We have a video game consisting of N stages. The i-th stage (1 \leq i \leq N) is composed of a movie lasting A_i minutes and gameplay lasting B_i minutes.

To clear the i-th stage for the first time, one must watch the movie and do the gameplay for that stage. For the second and subsequent times, one may skip the movie and do just the gameplay.

In the beginning, only the 1-st stage is unlocked, and clearing the i-th stage (1 \leq i \leq N - 1) unlocks the (i+1)-th stage.

Find the shortest time needed to clear a stage X times in total. Here, if the same stage is cleared multiple times, all of them count.

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
A_1 B_1
\vdots
A_N B_N

Output

Print the answer.

Sample Input 1

3 4
3 4
2 3
4 2

Sample Output 1

18

Here is one way to clear a stage 4 times in 18 minutes:

  • Clear Stage 1. It takes A_1 + B_1 = 7 minutes.
  • Clear Stage 2. It takes A_2 + B_2 = 5 minutes.
  • Clear Stage 2 again. It takes B_2= 3 minutes.
  • Clear Stage 2 again. It takes B_2= 3 minutes.

It is impossible to clear a stage 4 times within 17 minutes.

Sample Input 2

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

Sample Output 2

1000000076