Score : $400$ points

问题描述

我们有一个包含 $N$ 个关卡的电子游戏。第 $i$ 个关卡（$1 \leq i \leq N$）由一段持续时间为 $A_i$ 分钟的影片和一段持续时间为 $B_i$ 分钟的游戏环节组成。

首次通过第 $i$ 个关卡时，玩家必须观看该关卡的影片并进行游戏。从第二次及以后的尝试开始，玩家可以选择跳过影片，仅进行游戏环节。

最初，只有第 $1$ 个关卡是解锁状态，通关第 $i$ 个关卡 $(1 \leq i \leq N - 1)$ 将解锁第 $(i+1)$ 个关卡。

请找出总计通关某个关卡 $X$ 次所需的最短时间。这里需要注意的是，如果同一关卡被多次通关，所有次数都会被计算在内。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 10:57:36