Medicine

题目描述

Snuke 医生为高桥开了 $N$ 种药。从处方当天起的接下来的 $a_i$ 天（包括处方当天），他必须服用第 $i$ 种药物 $b_i$ 粒。他不必服用其他任何药物。 把处方当天记为第 $1$ 天。在第 $1$ 天或之后，第一次需要服用不超过 $K$ 粒药的那一天是哪一天？

输入格式

输入从标准输入按以下格式给出： $N$ $K$ $a_1$ $b_1$ $\vdots$ $a_N$ $b_N$

输出格式

如果高桥在第 $X$ 天（第 $1$ 天或之后）第一次需要服用不超过 $K$ 粒药，输出 $X$。

4 8
6 3
2 5
1 9
4 2

3

4 100
6 3
2 5
1 9
4 2

1

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

492686569

提示

$1 \leq N \leq 3 \times 10^5$ $0 \leq K \leq 10^9$ $1 \leq a_i,b_i \leq 10^9$ 所有输入值都是整数。在第 $1$ 天，他需要服用第 1 种、第 2 种、第 3 种和第 4 种药分别为 $3,5,9,$ 和 $2$ 粒。总共他在这一天需要服用 $19$ 粒，这不是不超过 $K(=8)$ 粒。
在第 $2$ 天，他需要服用第 1 种、第 2 种和第 4 种药分别为 $3,5$ 和 $2$ 粒。总共他在这一天需要服用 $10$ 粒，这不是不超过 $K(=8)$ 粒。
在第 $3$ 天，他需要服用第 1 种和第 4 种药分别为 $3$ 和 $2$ 粒。总共他在这一天需要服用 $5$ 粒，这在第 $1$ 次满足不超过 $K(=8)$ 粒。
因此，答案是 $3$。

标签: AtCoder|abc309C

来源

AtCoder|abc309C