Medicine

链接：C - Medicine (atcoder.jp)
来源：Atcoder

时间限制：2 seconds
空间限制：1024 megabytes

题目描述

医生给Takahashi开了N种药。对于第 \(i\) 种药丸，下面的 \(a_i\)天（包括开处方的当天），他必须服用 \(b_i\) 片药丸。他不必服用任何其他药物。

设开处方的那一天为第 \(1\) 天，在当天或之后的日子里，什么时候他会在这一天之后所需要吃的药丸数小于等于 \(K\) 个。

输入

输入按照这种形式输入：

N K

\(a_1\) \(b_1\)

.

.

.

\(a_N\) \(b_N\)

输出

如果Takahashi在第 \(X\) 天第一次所需要吃的药丸数量小于等于 \(K\) (\(X\) 为第一天或者之后的某一天)，输出 \(X\).

数据范围

\(1 \le N \le 3 \times 10^5\)

\(0 \le K \le 10^9\)

\(1 \le a_i, b_i \le 10^9\)

所有输入的数都是整数。

样例

输入样例1

4 8
6 3
2 5
1 9
4 2

输出样例1

3

样例解释

第一天，所需要吃的药丸数：\(3+5+9+2 = 19 > K\);

第二天，所需要吃的药丸数：\(3+5+2 = 10 > K\);

第三天，所需要吃的药丸数：\(3+2 = 5 \le K\).

所以答案为 \(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