题目描述

有一款游戏，共有 $N$ 个关卡。最开始只有第 $1$ 个关卡是解锁的。在第 $i$ 个关卡过关之后，才能解锁第 $i+1$ 个关卡，

每关由一部持续 $A_i$ 分钟的过场动画和持续 $B_i$ 分钟的游戏组成。解锁的关卡可以反复再过关。

第一次过关第 $i$ 个关卡时，必须观看过场动画并通关。对于第二次及以后过第 $i$ 个关卡，可以跳过过场动画，直接进行游戏。

找出通关 $X$ 次所需的最短时间。（ $X$ 次中可以是已通过的关卡再次通关。）

输入格式

输入格式如下：

$N$ $X$

$A_1$ $B_1$

$\vdots$

$A_N$ $B_N$

输出格式

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

样例 #1

样例输入 #1

3 4
3 4
2 3
4 2

样例输出 #1

18

样例 #2

样例输入 #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

提示

样例说明 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\ \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$
• 所有输入均为整数。