Score : $300$ points

问题描述

有 $10^{100}+1$ 个村庄，分别标记为数字 $0$, $1$, $\ldots$, $10^{100}$。

对于每个整数 $i$，在 $0$ 和 $10^{100}-1$（包含）之间，您可以在第 $i$ 个村庄支付 $1$ 日元（货币）以到达第 $(i + 1)$ 个村庄。除此之外，没有其他方式在村庄之间移动。

太郎现在拥有 $K$ 日元，并且位于第 $0$ 个村庄。他将尽力前往标记数字尽可能大的一个村庄。

他有 $N$ 位朋友。第 $i$ 位朋友正在第 $A_i$ 个村庄，当太郎到达第 $A_i$ 个村庄时，该朋友会给他 $B_i$ 日元。

请找出太郎最终能够到达的最后一个村庄所标记的数字。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $10^{100}+1$ villages, labeled with numbers $0$, $1$, $\ldots$, $10^{100}$.
For every integer $i$ between $0$ and $10^{100}-1$ (inclusive), you can pay $1$ yen (the currency) in Village $i$ to get to Village $(i + 1)$. There is no other way to travel between villages.

Taro has $K$ yen and is in Village $0$ now. He will try to get to a village labeled with as large a number as possible.
He has $N$ friends. The $i$-th friend, who is in Village $A_i$, will give Taro $B_i$ yen when he reaches Village $A_i$.
Find the number with which the last village he will reach is labeled.

Constraints

• $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$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$

$A_1$ $B_1$

$:$

$A_N$ $B_N$

Output

Print the answer.

Sample Input 1

2 3
2 1
5 10

Sample Output 1

4

Takahashi will travel as follows:

• Go from Village $0$ to Village $1$, for $1$ yen. Now he has $2$ yen.
• Go from Village $1$ to Village $2$, for $1$ yen. Now he has $1$ yen.
• Get $1$ yen from the $1$-st friend in Village $2$. Now he has $2$ yen.
• Go from Village $2$ to Village $3$, for $1$ yen. Now he has $1$ yen.
• Go from Village $3$ to Village $4$, for $1$ yen. Now he has $0$ yen, and he has no friends in this village, so his journey ends here.

Thus, we should print $4$.

Sample Input 2

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

Sample Output 2

6000000000

Note that the answer may not fit into a $32$-bit integer.

Sample Input 3

3 2
5 5
2 1
2 2

Sample Output 3

10

He may have multiple friends in the same village.

update @ 2024/3/10 09:15:38