奖杯

题目描述

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

输出格式

输出答案。

样例

3 4
3 4
2 3
4 2

18

下面是在 $18$ 分钟内通关 $4$ 次的一种方法:

通关第 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

数据范围

• $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$
• 输入中的所有值均为整数。