药物

题目描述

医生 Snuke 给高桥君开了 $N$ 种药物。在接下来的 $a_i$ 天里(包括开药当天),他需要每天服用第 $i$ 种药物 $b_i$ 粒。除此之外不需要服用任何其他药物。

设开药当天为第 $1$ 天。从第 $1$ 天开始,他第一次每天需要服用的药量不超过 $K$ 粒是在哪一天?

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$a_1$ $b_1$
$\vdots$
$a_N$ $b_N$

输出格式

设从第 $1$ 天开始,第一次每天需要服用的药量不超过 $K$ 粒是在第 $X$ 天,输出 $X$。

样例

4 8
6 3
2 5
1 9
4 2

3

第 $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$ 粒,首次满足不超过 $K(=8)$ 粒。

因此答案为 $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$
• 输入中的所有值均为整数。