Friends and Travel costs

题目描述

有 $10^{100}+1$ 个村庄，编号为 $0,1,\ldots,10^{100}$。
对于每个介于 $0$ 与 $10^{100}-1$（含端点）之间的整数 $i$，你可以在村庄 $i$ 支付 $1$ 日元（货币）到达村庄 $(i + 1)$。 没有其他方式在村庄之间旅行。 太郎现在在村庄 $0$，手头有 $K$ 日元。他将尽量到达编号尽可能大的村庄。
他有 $N$ 个朋友。第 $i$ 个朋友在村庄 $A_i$，当他到达村庄 $A_i$ 时会给太郎 $B_i$ 日元。
求他最终到达的最后一个村庄的编号。

输入格式

输入按下列格式自标准输入给出： $N$ $K$ $A_1$ $B_1$ : $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 \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$ 输入中的所有数值均为整数。Takahashi 的旅行过程如下：

从村庄 $0$ 到村庄 $1$，花费 $1$ 日元。现在他有 $2$ 日元。 从村庄 $1$ 到村庄 $2$，花费 $1$ 日元。现在他有 $1$ 日元。 在村庄 $2$ 从第 $1$ 个朋友那里得到 $1$ 日元。现在他有 $2$ 日元。 从村庄 $2$ 到村庄 $3$，花费 $1$ 日元。现在他有 $1$ 日元。 从村庄 $3$ 到村庄 $4$，花费 $1$ 日元。现在他有 $0$ 日元，并且在该村庄没有朋友，所以他的旅程在此结束。

因此，我们应该输出 $4$。
注意答案可能无法适配 $32$ 位整数。
他可能在同一村庄有多个朋友。

标签: AtCoder|abc203C

来源

AtCoder|abc203C