0287 - ダンジョン (Dungeon)

問題

　あなたはあるダンジョンの地下 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)．
　どの採点用データにおいても, 地下 N 階にたどり着く方法が存在する．採点用データのうち, 配点の 10%分については, N ≤ 1000 かつ H ≤ 1000 を満たす．配点の 30%分については, N ≤ 1000 を満たす．配点の 50%分については, 泉の使用回数の最小値が 10⁶ を超えない.

出力

　体力を 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