{"raw_statement":[{"iden":"problem statement","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?"},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"4 8\n6 3\n2 5\n1 9\n4 2"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"4 100\n6 3\n2 5\n1 9\n4 2"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"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"},{"iden":"sample output 3","content":"492686569"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}