← 返回题目列表

AtCoder · abc258_d

G. 奖杯

中文机器翻译题面 查看原题

分数: 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