/ 
Time Limit: 3.5 sec / Memory Limit: 1024 MB
配点 : 525 点
問題文
あなたの前に体力 H のモンスターが現れ、ターン制の戦闘が開始しました。
あなたは、ターン 1,2,… のそれぞれに呪文 1,…,N の N 種類の呪文のうち一つを唱えます。
ターン i に呪文 j を唱えると、その呪文の効果としてターン i,i+1,…,i+t_j －1 のそれぞれでモンスターの体力が d_j 減ります。
モンスターの体力を 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
出力例 2
9
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