Score : $350$ points

问题陈述

医生Snuke为高桥开了$N$种药。从开药的那天（包括开药的那天）起，在接下来的$a_i$天内，他必须服用第$i$种药的$b_i$片药片。他不需要服用任何其他药物。

假设开药的那天为第$1$天。在第$1$天或之后，他必须服用$K$片或更少药片的第一天是什么时候？

以上为 kimi GPT 翻译，仅供参考。

Problem Statement

Snuke the doctor prescribed $N$ kinds of medicine for Takahashi. For the next $a_i$ days (including the day of the prescription), he has to take $b_i$ pills of the $i$-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day $1$. On or after day $1$, when is the first day on which he has to take $K$ pills or less?

Constraints

• $1 \leq N \leq 3 \times 10^5$
• $0 \leq K \leq 10^9$
• $1 \leq a_i,b_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $K$

$a_1$ $b_1$

$\vdots$

$a_N$ $b_N$

Output

If Takahashi has to take $K$ pills or less on day $X$ for the first time on or after day $1$, print $X$.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day $1$, he has to take $3,5,9$, and $2$ pills of the $1$-st, $2$-nd, $3$-rd, and $4$-th medicine, respectively. In total, he has to take $19$ pills on this day, which is not $K(=8)$ pills or less. On day $2$, he has to take $3,5$, and $2$ pills of the $1$-st, $2$-nd, and $4$-th medicine, respectively. In total, he has to take $10$ pills on this day, which is not $K(=8)$ pills or less. On day $3$, he has to take $3$ and $2$ pills of the $1$-st and $4$-th medicine, respectively. In total, he has to take $5$ pills on this day, which is $K(=8)$ pills or less for the first time.

Thus, the answer is $3$.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 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

Sample Output 3

492686569

update @ 2024/3/10 08:45:57