朋友和旅费

题目描述

有 $10^{100}+1$ 个村庄,编号为 $0$, $1$, $\ldots$, $10^{100}$。

对于满足 $0 \le i \le 10^{100}-1$ 的每个整数 $i$,都可以在村庄 $i$ 支付 $1$ 日元(货币单位)到达村庄 $i+1$。 村庄之间没有其他移动方式。

太郎现在在村庄 $0$,持有 $K$ 日元。他想要尽量到达编号尽可能大的村庄。

他有 $N$ 个朋友。第 $i$ 个朋友在村庄 $A_i$,当他到达村庄 $A_i$ 时会给他 $B_i$ 日元。

求他最后能到达的村庄的编号。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

输出格式

输出答案。

样例

2 3
2 1
5 10

4

高桥君的移动过程如下:

从村庄 $0$ 到村庄 $1$,支付 $1$ 日元。现在他有 $2$ 日元。

从村庄 $1$ 到村庄 $2$,支付 $1$ 日元。现在他有 $1$ 日元。

在村庄 $2$ 从第 $1$ 个朋友那里得到 $1$ 日元。现在他有 $2$ 日元。

从村庄 $2$ 到村庄 $3$,支付 $1$ 日元。现在他有 $1$ 日元。

从村庄 $3$ 到村庄 $4$,支付 $1$ 日元。现在他有 $0$ 日元,而且这个村庄里没有朋友,所以他的旅程到此结束。

因此,应输出 $4$。

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

6000000000

注意答案可能无法放入 $32$ 位整数。

3 2
5 5
2 1
2 2

10

同一个村庄可能有多个朋友。

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le K \le 10^9$
• $1 \le A_i \le 10^{18}$
• $1 \le B_i \le 10^9$
• 输入均为整数