题目描述

有一款游戏，共有 $N$ 个关卡。最开始只有第 $1$ 个关卡是解锁的。在第 $i$ 个关卡过关之后，才能解锁第 $i+1$ 个关卡，每关由一部持续 $A$ 分钟的过场动画和持续 $B$ 分钟的游戏组成。

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

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

输入格式

第一行输入 $N$ $X$

接下来 $N$ 行每行两个整数分别是 $A_i$ $B_i$

输出格式

输出一个整数代表答案

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\ \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$

样例 1 解释

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

• 通关阶段 $1$ 。需要 $A_1 + B_1 = 7$ 分钟。
• 通关阶段 $2$ 。耗时 $A_2 + B_2 = 5$ 分钟。
• 再次通关阶段 $2$ 。耗时 $B_2= 3$ 分钟
• 再次通关阶段 $2$ 。耗时 $B_2= 3$ 分钟

不可能在 $17$ 分钟内通关 $4$ 次。