4084: 朋友和旅行成本
内存限制：1024 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
# Friends and Travel costs
## 题目描述
有$10^{100}+1$个村庄,编号从0到$10^{100}$。对于每个整数$i(0≤i≤10^{100}-1$),小高可以在村庄$i$支付1元前往村庄$(i+1)$。这是村庄之间唯一的旅行方式。小高现在有$K$元,位于村庄0。他将尝试到达编号尽可能大的村庄。他有$N$个朋友。第$i$个朋友在村庄$A_i$,当小高到达村庄$A_i$时会给他$B_i$元。请找出小高最终能到达的村庄编号。
输入
## 输入格式
输入从标准输入按以下格式给出:
$N \ K$
$A_1 \ B_1$
$A_2 \ B_2$
:
$A_N \ B_N$
输出
## 输出格式
输出所求的答案。
样例输入 复制
2 3
2 1
5 10样例输出 复制
4提示
## 输入输出样例
### 输入样例1
```
2 3
2 1
5 10
```
### 输出样例1
```
4
```
### 输入样例2
```
5 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000
```
### 输出样例2
```
6000000000
```
### 输入样例3
```
3 2
5 5
2 1
2 2
```
### 输出样例3
```
10
```
## 数据范围与提示
【样例1说明】
小高的旅程如下:
- 从村庄 0 到村庄 1,花费 1 元。现在他有 2 元。
- 从村庄 1 到村庄 2,花费 1 元。现在他有 1 元。
- 在村庄 2 获得第 1 个朋友给的 1 元。现在他有 2 元。
- 从村庄 2 到村庄 3,花费 1 元。现在他有 1 元。
- 从村庄 3 到村庄 4,花费 1 元。现在他有 0 元,且在这个村庄没有朋友,所以旅程在这里结束。
因此,我们应该输出 4。
【样例2说明】
注意答案可能不适合 32 位整数。
【样例3说明】
同一个村庄可能有多个朋友。
【数据范围】
$1 \leq N \leq 2 \times 10^5,1 \leq K \leq 10^9,1 \leq A_i \leq 10^{18},1 \leq B_i \leq 10^9$，所有输入均为整数。
## 题目来源
ABC203C