atcoder#ABC303F. [ABC303F] Damage over Time

[ABC303F] Damage over Time

配点 : 525525

問題文

あなたの前に体力 HH のモンスターが現れ、ターン制の戦闘が開始しました。

あなたは、ターン 1,2,1,2, \cdots のそれぞれに呪文 1,,N1, \cdots ,NNN 種類の呪文のうち一つを唱えます。

ターン ii に呪文 jj を唱えると、その呪文の効果としてターン i,i+1,,i+tj1i,i+1, \cdots ,i+t_j -1 のそれぞれでモンスターの体力が djd_j 減ります。

モンスターの体力を 00 以下にすることが可能な最も早いターンを求めてください。

制約

  • 1N3×1051 \leq N \leq 3 \times 10^5
  • 1H10181 \leq H \leq 10^{18}
  • 1ti,di1091 \leq t_i,d_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

NN HH

t1t_1 d1d_1

\vdots

tNt_N dNd_N

出力

答えを出力せよ。

2 20
2 2
5 1
6

以下のようにするとターン 66 にモンスターの体力を 00 以下に出来ます。これが最も早いターンです。

  • ターン 11 に魔法 11 を使う。ターン 11 に使った魔法の効果でモンスターの体力が 22 減り、1818 になる。
  • ターン 22 に魔法 22 を使う。ターン 1,21,2 に使った魔法の効果でモンスターの体力が 2+1=32+1=3 減り、1515 になる。
  • ターン 33 に魔法 11 を使う。ターン 2,32,3 に使った魔法の効果でモンスターの体力が 1+2=31+2=3 減り、1212 になる。
  • ターン 44 に魔法 22 を使う。ターン 2,3,42,3,4 に使った魔法の効果でモンスターの体力が 1+2+1=41+2+1=4 減り、88 になる。
  • ターン 55 に魔法 11 を使う。ターン 2,4,52,4,5 に使った魔法の効果でモンスターの体力が 1+1+2=41+1+2=4 減り、44 になる。
  • ターン 66 に魔法 22 を使う。ターン 2,4,5,62,4,5,6 に使った魔法の効果でモンスターの体力が 1+1+2+1=51+1+2+1=5 減り、1-1 になる。
10 200
1 21
1 1
1 1
8 4
30 1
3 1
10 2
8 1
9 1
4 4
9