{"problem":{"name":"Medicine","description":{"content":"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 t","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc309_c"},"statements":[{"statement_type":"Markdown","content":"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.\nLet 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?\n\n## Constraints\n\n*   $1 \\leq N \\leq 3 \\times 10^5$\n*   $0 \\leq K \\leq 10^9$\n*   $1 \\leq a_i,b_i \\leq 10^9$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n$a_1$ $b_1$\n$\\vdots$\n$a_N$ $b_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc309_c","tags":[],"sample_group":[["4 8\n6 3\n2 5\n1 9\n4 2","3\n\nOn 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.  \nOn 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.  \nOn 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.\nThus, the answer is $3$."],["4 100\n6 3\n2 5\n1 9\n4 2","1"],["15 158260522\n877914575 2436426\n24979445 61648772\n623690081 33933447\n476190629 62703497\n211047202 71407775\n628894325 31963982\n822804784 50968417\n430302156 82631932\n161735902 80895728\n923078537 7723857\n189330739 10286918\n802329211 4539679\n303238506 17063340\n492686568 73361868\n125660016 50287940","492686569"]],"created_at":"2026-03-03 11:01:14"}}