5564번 - ダンジョン 다국어

문제

あなたはあるダンジョンの地下 N 階にある財宝を手に入れたいと思っている.最 初,あなたは地下 1 階におり,あなたの体力は H(H は正整数) である.下の階に降 りるときに,体力が消費される.あらかじめ各階における下の階に降りるときに消 費される体力が分かっている.一方,各階には 1 つの回復の泉があり,泉を 1 回使う ごとに回復できる体力がそれぞれ定まっている.体力が 0 以下になるとあなたは死 んでしまう.また,体力が H よりも高くなることはない.回復の泉は何回でも使う ことができるが,回復には時間がかかるので,あなたは泉の使用回数をできるだけ 少なくしたいと考えている.

N,H,各階の下の階に降りるときに消費される体力,そして各階で回復の泉を 1 回使用したときに回復する体力が与えられたとき,体力を 0 以下にすることなく地 下 N 階まで到達するために必要な泉の使用回数の最小値を求めるプログラムを作成 せよ.

また,一度下の階に降りると,財宝を手に入れるまで上の階に戻ることはできない.

입력

入力はN 行からなる.入力の1行目には2つの整数N, H(2 ≤ N ≤ 100000 = 10⁵, 1 ≤ H ≤ 10000000 = 10⁷) が空白を区切りとして書かれている.N は地下 N 階に財宝が あるということを表し,H は初期体力 ( ダンジョンの地下 1 階に到着した段階の体 力 ) であり,かつ体力の最大値である ( 回復によって体力が H より大きくなること はない ) .

続く N − 1 行には,2 つの整数が空白を区切りとして書かれている.1 + i 行目 (1 ≤ i ≤ N − 1) の整数 d_i, h_i について, d_i は地下 i 階から地下 i + 1 階に降りる際 に消費される体力を,h_i は地下 i 階で泉を 1 回使用したときに回復する体力を表す (0 ≤ d_i < H, 1 ≤ h_i < H).

출력

体力を 0 以下にすることなく地下 N 階に到達するために必要な, 泉の使用回数の最小値を含む 1 行からなる.

제한

힌트

この問題では,扱う整数の範囲が 32bit に収まらない可能性があることに注意せよ.