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