AT_abc309_c [ABC309C] Medicine

题目描述

高桥君从医生すぬけ君那里收到了 $N$ 种药的处方。第 $i$ 种药需要从处方当天起（包括当天）连续 $a_i$ 天，每天服用 $b_i$ 片。此外，高桥君不需要服用其他药物。

将处方当天记为第 $1$ 天。请你求出，从第 $1$ 天起，第一次高桥君当天需要服用的药片总数不超过 $K$ 片的是第几天。

输入格式

输入以如下格式从标准输入给出。

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

输出格式

若第 $X$ 天起，高桥君当天需要服用的药片总数首次不超过 $K$ 片，请输出 $X$。

输入输出样例 #1

输入 #1

4 8
6 3
2 5
1 9
4 2

输出 #1

3

输入输出样例 #2

输入 #2

4 100
6 3
2 5
1 9
4 2

输出 #2

1

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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$ 天，高桥君需要服用第 $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$。

由 ChatGPT 4.1 翻译