{"raw_statement":[{"iden":"problem statement","content":"A monster with health $H$ has appeared in front of you, and a turn-based battle has started.\nIn each turn $1,2,…$, you cast one of $N$ spells, spells $1,…,N$.\nIf you cast spell $i$ in turn $j$, the monster's health reduces by $d_i$ in each turn $j,j+1,…,j+t_i －1$.\nFind the earliest turn that you can make the monster's health $0$ or less."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 3 \\times 10^5$\n*   $1 \\leq H \\leq 10^{18}$\n*   $1 \\leq t_i,d_i \\leq 10^9$\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $H$\n$t_1$ $d_1$\n$\\vdots$\n$t_N$ $d_N$"},{"iden":"sample input 1","content":"2 20\n2 2\n5 1"},{"iden":"sample output 1","content":"6\n\nThe following procedure makes the monster's health $0$ or less in turn $6$, which is the earliest.\n\n*   Cast spell $1$ in turn $1$. Due to the spell cast in turn $1$, the monster's health reduces by $2$ and becomes $18$.\n*   Cast spell $2$ in turn $2$. Due to the spells cast in turns $1$ and $2$, the monster's health reduces by $2+1=3$ and becomes $15$.\n*   Cast spell $1$ in turn $3$. Due to the spells cast in turns $2$ and $3$, the monster's health reduces by $1+2=3$ and becomes $12$.\n*   Cast spell $2$ in turn $4$. Due to the spells cast in turns $2,3$ and $4$, the monster's health reduces by $1+2+1=4$ and becomes $8$.\n*   Cast spell $1$ in turn $5$. Due to the spells cast in turns $2,4$ and $5$, the monster's health reduces by $1+1+2=4$ and becomes $4$.\n*   Cast spell $2$ in turn $6$. Due to the spells cast in turns $2,4,5$ and $6$, the monster's health reduces by $1+1+2+1=5$ and becomes $-1$."},{"iden":"sample input 2","content":"10 200\n1 21\n1 1\n1 1\n8 4\n30 1\n3 1\n10 2\n8 1\n9 1\n4 4"},{"iden":"sample output 2","content":"9"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}