AT_abc258_d [ABC258D] Trophy

题目描述

有一个包含 $N$ 个关卡的游戏，第 $i$ 个关卡由 $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

输入 #1

3 4
3 4
2 3
4 2

输出 #1

18

输入输出样例 #2

输入 #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

说明/提示

限制条件

• $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$
• 输入均为整数

样例解释 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$ 次通关。

由 ChatGPT 4.1 翻译