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

输入 #1

2 3
2 1
5 10

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

6000000000

输入输出样例 #3

输入 #3

3 2
5 5
2 1
2 2

输出 #3

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

样例解释 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 翻译