题目描述

有 $10^{100} + 1$ 个村子排成一行，编号为 $0, 1, 2, \cdots, 10^{100}$。对于每个整数 $i(0\le i\le 10^{100}-1)$，小高可以在村庄 $i$ 支付 $1$ 元前往村庄 $(i+1)$。这是村庄之间唯一的旅行方式。

小高现在有 $K$ 元，位于村庄 $0$。他将尝试到达编号尽可能大的村庄。他有 $N$ 个朋友，第 $i$ 个朋友在村庄 $A_i$，当小高到达村庄 $A_i$ 时会给他 $B_i$ 元。

请找出小高最终能到达的村庄编号。不考虑赊账。

输入格式

第一行输入两个整数 $N,K$。

接下来有 $N$ 行，每行两个整数 $A_i,B_i$。

输出格式

输出所求的答案。

样例

2 3
2 1
5 10

4

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

6000000000

3 2
5 5
2 1
2 2

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$
• 所有输入均为整数。