Damage over Time

AtCoder
IDabc303_f
Time3500ms
Memory256MB
Difficulty
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 monster's health reduces by $d_i$ in each turn $j,j+1,…,j+t_i -1$. Find the earliest turn that you can make the monster's health $0$ or less. ## Constraints * $1 \leq N \leq 3 \times 10^5$ * $1 \leq H \leq 10^{18}$ * $1 \leq t_i,d_i \leq 10^9$ * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $H$ $t_1$ $d_1$ $\vdots$ $t_N$ $d_N$ [samples]
Samples
Input #1
2 20
2 2
5 1
Output #1
6

The following procedure makes the monster's health $0$ or less in turn $6$, which is the earliest.

*   Cast spell $1$ in turn $1$. Due to the spell cast in turn $1$, the monster's health reduces by $2$ and becomes $18$.
*   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$.
*   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$.
*   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$.
*   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$.
*   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$.
Input #2
10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4
Output #2
9
API Response (JSON)
{
  "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 mo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments