C - 朋友和旅行费用

得分：300 分

问题描述

有 $10^{100}+1$ 个村庄，标号为 $0$，$1$，$\ldots$，$10^{100}$。
对于 $0$ 到 $10^{100}-1$（包含）之间的每个整数 $i$，你可以花费 $1$ 日元（货币）在村庄 $i$ 到达村庄 $(i + 1)$。 没有其他方式可以在村庄之间旅行。

太郎现在在村庄 $0$，他手上有 $K$ 日元。他将尽可能到达编号最大的村庄。
他有 $N$ 个朋友。第 $i$ 个朋友在村庄 $A_i$，将在他到达村庄 $A_i$ 时给予太郎 $B_i$ 日元。
找到太郎将到达的最后一个村庄的编号。

约束

• $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$
• 输入的所有值都是整数。

输入

从标准输入中按下列格式给出：

$N$ $K$

$A_1$ $B_1$

$:$

$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

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