题目描述

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

输出

输出答案。

示例输入1

3 4
3 4
2 3
4 2

示例输出1

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次。

示例输入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