4111: 电子游戏过关所需的最短时间
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
# Trophy
## 题目描述
小高正在玩一个由$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提示
## 输入输出样例
### 输入样例1
```
3 4
3 4
2 3
4 2
```
### 输出样例1
```
18
```
### 输入样例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 ≤ N ≤ 2 × 10^5$
- $1 ≤ A_i, B_i ≤ 10^9 (1 ≤ i ≤ N)$
- $1 ≤ X ≤ 10^9$
- 所有输入均为整数。
## 题目来源
ABC258D