该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有$10^{100}$个村子排成一行，编号为$0, 1, 2, \dots, 10^{100}-1$.

你在第$i(0 \leq i \lt 10^{100}-1$个村子，可以花费$1$元的代价到达下一个村子(可以是i-1，也可以是i+1)。没有其他的路径可以走。(举个例子，你在 2号村子，只能去1号村子或者3号村子)

你最开始在$0$号村子，手上有$K$元。你有$N$个朋友,第$i$个朋友在$A_i$村子，如果你到了那里，他会给你$B_i$元。问你最远能到达哪个村子。不考虑赊账。

输入格式

第一行输入 一个N和K，N表示N个朋友，K表示一开始有K元

接下来N行，每行输入一个$A_i$ 和 $B_i$表示第i个朋友的位置和他手上有的钱

输出格式

2 3
2 1
5 10

4

5 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
5 1000000000

6000000000

提示

数据范围如下：

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