← 返回题目列表

AtCoder · abc203_c

C. 朋友和旅行费用

中文机器翻译题面 查看原题

分数: 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

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