题目描述

小高正在玩一个由$N$个关卡组成的电子游戏。第$i$个关卡$(1 ≤ i ≤ N)$由一段持续$A_i$分钟的过场动画和一段持续$B_i$分钟的游戏内容组成。首次通关某个关卡时，必须观看过场动画并完成游戏内容。之后再次通关该关卡时，可以跳过过场动画，只需完成游戏内容。游戏开始时只有第1关可以游玩，通关第i关$(1 ≤ i ≤ N-1)$后会解锁第$(i+1)$关。请计算通关任意关卡共计$X$次所需的最短时间。

输入格式

输入格式如下：

$N$ $X$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_N$ $B_N$

输出格式

输出一个整数，表示通关任意关卡共计$X$次所需的最短时间。

样例

3 4
3 4
2 3
4 2

18

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

1000000076

样例1解释

以下是一种在18分钟内通关4次的方案：

1. 通关第1关，耗时$A_1 + B_1 = 7$分钟。

2. 通关第2关，耗时$A_2 + B_2 = 5$分钟。

3. 再次通关第2关，耗时$B_2 = 3$分钟。

4. 再次通关第2关，耗时$B_2 = 3$分钟。

无法在17分钟或更短时间内通关4次。

数据范围

• $1 ≤ N ≤ 2 × 10^5$
• $1 ≤ A_i, B_i ≤ 10^9 (1 ≤ i ≤ N)$
• $1 ≤ X ≤ 10^9$
• 所有输入均为整数。

来源

• AtCoder ABC258D