分数: 300 点
问题陈述
有 10^{100}+1 村庄,标有数字 0, 1, \ldots, 10^{100}.
对于每个整数 i 之间 0 和 10^{100}-1 (含),可以支付 1 村里的日元(货币) i 前往村庄 (i + 1)。
村庄之间没有其他交通方式。
太郎有 K 日元并且在村庄 0 现在。他将尝试到达标有尽可能多数字的村庄。
他有 N 朋友们。的 i第一个朋友,在村庄 A_i,会给太郎
当他到达村庄时 B_i 日元 A_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
输出
打印答案。
示例输入 1
2 3 2 1 5 10
示例输出 1
4
高桥的行程如下:
- 从村庄出发 0 到村 1,对于 1 日元。现在他有 2 日元。
- 从村庄出发 1 到村 2,对于 1 日元。现在他有 1 日元。
- 获取 1 日元从 1-村里的第一个朋友 2。现在他有 2 日元。
- 从村庄出发 2 到村 3,对于 1 日元。现在他有 1 日元。
- 从村庄出发 3 到村 4,对于 1 日元。现在他有 0 日元,而且他在这个村子里没有朋友,所以他的旅程到此结束。
因此,我们应该打印 4.
示例输入 2
5 1000000000 1 1000000000 2 1000000000 3 1000000000 4 1000000000 5 1000000000
示例输出 2
6000000000
请注意,答案可能不适合 32位整数。
示例输入 3
3 2 5 5 2 1 2 2
示例输出 3
10
他可能在同一个村庄有多个朋友。