103035: [Atcoder]ABC303 F - Damage over Time
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $525$ points
Problem Statement
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$
Output
Print the answer.
Sample Input 1
2 20 2 2 5 1
Sample 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$.
Sample Input 2
10 200 1 21 1 1 1 1 8 4 30 1 3 1 10 2 8 1 9 1 4 4
Sample Output 2
9
Input
题意翻译
有一只血量为 $H$ 的怪兽，你现在要攻击它。你有 $N$ 种方式可以攻击它。 如果你在时间 $j$ 用了第 $i$ 种方式攻击，那么在时间 $j,j+1,\cdots j+t_i-1$，它都会受到 $d_i$ 点伤害。 问最少需要花多少时间才能使怪兽的血量不高于 $0$。Output
得分：$525$分
部分
问题描述
一只生命值为$H$的怪物出现在你面前，一场回合制战斗开始了。
在每个回合$1,2,…$，你施放其中一个$N$个法术，法术$1,…,N$。
如果你在回合$j$施放法术$i$，怪物的生命值在每个回合$j,j+1,…,j+t_i －1$都会减少$d_i$。
找出你能让怪物的生命值为$0$或更低的最早的回合。
部分
约束
* $1 \leq N \leq 3 \times 10^5$
* $1 \leq H \leq 10^{18}$
* $1 \leq t_i,d_i \leq 10^9$
* 输入中的所有值都是整数。
部分
输入
输入按照以下格式从标准输入给出：
$N$ $H$
$t_1$ $d_1$
$\vdots$
$t_N$ $d_N$
部分
输出
打印答案。
部分
样例输入 1
```
2 20
2 2
5 1
```
部分
样例输出 1
```
6
```
以下程序可以在第6个回合让怪物的生命值为0或更低，这是最早的回合。
* 在第1个回合施放法术$1$。由于在第1个回合施放的法术，怪物的生命值减少2，变为$18$。
* 在第2个回合施放法术$2$。由于在第1个和第2个回合施放的法术，怪物的生命值减少$2+1=3$，变为$15$。
* 在第3个回合施放法术$1$。由于在第2个和第3个回合施放的法术，怪物的生命值减少$1+2=3$，变为$12$。
* 在第4个回合施放法术$2$。由于在第2,3和第4个回合施放的法术，怪物的生命值减少$1+2+1=4$，变为$8$。
* 在第5个回合施放法术$1$。由于在第2,4和第5个回合施放的法术，怪物的生命值减少$1+1+2=4$，变为$4$。
* 在第6个回合施放法术$2$。由于在第2,4,5和第6个回合施放的法术，怪物的生命值减少$1+1+2+1=5$，变为$-1$。
部分
样例输入 2
```
10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4
```