Trophy

题目描述

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

输出格式

输出答案。

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$ 输入中的所有值均为整数。下面是一种在 $18$ 分钟内通关某个关卡 $4$ 次的方法：

通关关卡 $1$。耗时 $A_1 + B_1 = 7$ 分钟。 通关关卡 $2$。耗时 $A_2 + B_2 = 5$ 分钟。 再次通关关卡 $2$。耗时 $B_2= 3$ 分钟。 再次通关关卡 $2$。耗时 $B_2= 3$ 分钟。

在 $17$ 分钟内不可能通关某个关卡 $4$ 次。

标签: AtCoder|abc258D

来源

AtCoder|abc258D