103092: [Atcoder]ABC309 C - Medicine

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 $9$ 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

问题描述

医生Snuke给Takahashi开了$N$种药。接下来的$a_i$天（包括开药当天），他需要服用第$i$种药的$b_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$

输出

如果Takahashi在第$X$天或之后第一次需要服用$K$片或更少药片，打印$X$。

样例输入1

4 8
6 3
2 5
1 9
4 2

样例输出1

3

在第$1$天，他需要服用第$1$种药的$3$片、第$2$种药的$5$片、第$3$种药的$9$片和第$4$种药的$2$片。总共需要服用$19$片药，这不等于或小于$K(=8)$片药。
在第$2$天，他需要服用第$1$种药的$3$片、第$2$种药的$5$片和第$4$种药的$2$片。总共需要服用$10$片药，这不等于或小于$K(=8)$片药。
在第$3$天，他需要服用第$1$种药的$3$片和第$4$种药的$2$片。总共需要服用$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