{"problem":{"name":"Damage over Time","description":{"content":"A monster with health $H$ has appeared in front of you, and a turn-based battle has started. In each turn $1,2,…$, you cast one of $N$ spells, spells $1,…,N$. If you cast spell $i$ in turn $j$, the mo","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc303_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc303_f","tags":[],"sample_group":[["2 20\n2 2\n5 1","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$."],["10 200\n1 21\n1 1\n1 1\n8 4\n30 1\n3 1\n10 2\n8 1\n9 1\n4 4","9"]],"created_at":"2026-03-03 11:01:13"}}