102583: [AtCoder]ABC258 D - Trophy

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

问题描述

我们有一个包含$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