分数: 400 点
问题陈述
我们有一个视频游戏,包括 N 阶段。的 i-第阶段 (1 \leq i \leq N) 由一部持久的电影组成 A_i 分钟和游戏持久 B_i 分钟。
清除 i第一个阶段,第一次,必须观看电影并进行该阶段的游戏。对于第二次和随后的时间,人们可以跳过电影而只玩游戏。
一开始,只有 1-st 阶段已解锁,并清除 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
这是清理关卡的一种方法 4 次 18 分钟:
- 清除舞台 1。这需要 再次 A_1 + B_1 = 7 分钟。
- 清除舞台 2。这需要 再次 A_2 + B_2 = 5 分钟。
- 清除舞台 2 。这需要 B_2= 3 分钟。
- 清除舞台 2 。这需要 B_2= 3 分钟。
不可能通关 4 次内 17 分钟。
示例输入 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