AT_abc203_c [ABC203C] Friends and Travel costs

有 $10^{100}+1$ 个村庄，分别编号为村庄 $0$、村庄 $1$、$\ldots$、村庄 $10^{100}$。 对于所有 $0$ 到 $10^{100}-1$ 之间的整数 $i$，你可以支付 $1$ 日元从村庄 $i$ 移动到村庄 $(i+1)$。除此之外，没有其他移动方式。 太郎君一开始带着 $K$ 日元站在村庄 $0$，他想尽可能前进到编号最大的村庄。 太郎君有 $N$ 个朋友，第 $i$ 个朋友在村庄 $A_i$，当太郎君到达村庄 $A_i$ 时，这个朋友会给太郎君 $B_i$ 日元。 请你求出太郎君最终能够到达的村庄编号。

输入通过标准输入给出，格式如下： > $N$ $K$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_N$ $B_N$

请输出答案。

## 限制条件 - $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$ - 所有输入均为整数。 ## 样例解释 1 太郎君的行动如下： - 从村庄 $0$ 支付 $1$ 日元前往村庄 $1$，剩余 $2$ 日元。 - 从村庄 $1$ 支付 $1$ 日元前往村庄 $2$，剩余 $1$ 日元。 - 在村庄 $2$ 收到第 $1$ 个朋友给的 $1$ 日元，剩余 $2$ 日元。 - 从村庄 $2$ 支付 $1$ 日元前往村庄 $3$，剩余 $1$ 日元。 - 从村庄 $3$ 支付 $1$ 日元前往村庄 $4$，剩余 $0$ 日元。此时村庄 $4$ 没有朋友，因此停在村庄 $4$。 因此，输出 $4$。 ## 样例解释 2 请注意，答案可能无法用 $32$ 位整数表示。 ## 样例解释 3 同一个村庄可能有多个朋友。 由 ChatGPT 4.1 翻译