← 返回题目列表

AtCoder · abc309_c

F. 医学

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

分数: 350 点

问题陈述

克制医生开出的处方 N 高桥种药。 对于接下来的 a_i 天(包括处方当天),他必须服用 b_i 药丸 i第药。 他不需要服用任何其他药物。

设处方日为日 1。 当日或之后 1,他必须服用的第一天是什么时候 K 药片还是更少?

约束

  • 1 \leq N \leq 3 \times 10^5
  • 0 \leq K \leq 10^9
  • 1 \leq a_i,b_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
a_1 b_1
\vdots
a_N b_N

输出

如果高桥必须采取 K 当天服药或更少 X 当天或之后首次 1,打印 X.


示例输入 1

4 8
6 3
2 5
1 9
4 2

示例输出 1

3

当天 1,他必须采取 3,5,9,和 2 药丸 1-st, 2-nd, 3-rd,和 4第药分别。 总共,他必须采取 19 这一天吃药,这不是 K(=8) 丸或更少。
当天 2,他必须采取 3,5,和 2 药丸 1-st, 2-nd,和 4第药分别。 总共,他必须采取 10 这一天吃药,这不是 K(=8) 丸或更少。
当天 3,他必须采取 3 和 2 药丸 1-st 和 4第药分别。 总共,他必须采取 5 这一天的药丸,即 K(=8) 第一次服用药丸或更少。

因此,答案是 3.


示例输入 2

4 100
6 3
2 5
1 9
4 2

示例输出 2

1

示例输入 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

示例输出 3

492686569