当前没有测试数据。

D - 奖杯

分数：$400$ 分

问题描述

我们有一个包含 $N$ 个关卡的视频游戏。第 $i$ 个关卡 $(1 \leq i \leq N)$ 由一个持续时间为 $A_i$ 分钟的电影和一个持续时间为 $B_i$ 分钟的游戏组成。

要第一次通过第 $i$ 个关卡，必须观看电影并进行游戏。对于第二次及以后通过关卡，可以跳过电影只进行游戏。

一开始，只有第 $1$ 个关卡是解锁的，通过第 $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$

输出

输出答案。

3 4
3 4
2 3
4 2

18

以下是完成 4 次关卡的一种方式，所需时间为 18 分钟：

• 通过第 1 个关卡。花费的时间为 $A_1 + B_1 = 7$ 分钟。
• 通过第 2 个关卡。花费的时间为 $A_2 + B_2 = 5$ 分钟。
• 再次通过第 2 个关卡。花费的时间为 $B_2 = 3$ 分钟。
• 再次通过第 2 个关卡。花费的时间为 $B_2 = 3$ 分钟。

无法在 17 分钟内通过 4 次关卡。

10 1000000000
3 3
1 6
4 7
1 8
5 7
9 9
2 4
6 4
5 1
3 1

1000000076