题目描述

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

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

来源

• AtCoder ABC203C