Dungeon

Time Limit : 8 sec, Memory Limit : 65536 KB

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。

ダンジョン

問題

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

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

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

入力

入力ファイルのファイル名は input.txt である.

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

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

どの採点用データにおいても,地下 N 階にたどり着く方法が存在する.採点用デー タのうち,配点の 10%分については,N ≤ 1000 かつ H ≤ 1000 を満たす.配点の 30%分については,N ≤1000 を満たす.配点の 50%分については,泉の使用回数の 最小値が 106 を超えない.

出力

出力ファイルのファイル名は output.txt である.

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

注意

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

入出力例

入力例 1
10 10
4 2
2 5
6 1
7 3
6 4
9 6
0 8
4 1
9 4
  
 
出力例 1
10
   

Notes on Submission

標準入出力を行うプログラムを作成して下さい.


Source: 9th Japanese Olympiad in Informatics , 2010-02-14
http://www.ioi-jp.org/