010 - ゲームの攻略
時間制限 2 秒 / メモリ制限 256 MB / 得点 20 / x 0 /
問題
あなたは所属するプログラミング部の部室から古びたボードゲームを発見しました。面白そうなので遊んでみることにしました。
このゲームは M 個のイベントから成り、時刻 ti にイベント i を攻略しなければいけません。ただし、そのときにあなたの強さは si 以上である必要があり、si 以上にできない場合はゲームオーバーになります。ゲーム開始時(時刻0)のあなたの強さは0ですが、アイテムを買うことで強さを増加させることができます。ゲーム開始時のあなたの所持金は0ですが、1単位時間あたり1増加します。
ボードにはそれぞれ1から N の番号が付けられた N 個のアイテムが順番に並べられており、アイテム i の値段は vi で、それを購入するとあなたの強さが hi 増加します。アイテムは所持金が十分であれば好きな時刻に好きな数だけ購入することができますが、残っているアイテムの中で番号が小さいものから順に選ばなければなりません。各アイテムは1度購入すると消滅します。
また、同じ時刻に複数のアイテムを連続で買うことができ、このとき隣り合うアイテムの hi の差分の和をボーナスとして得ることができます。例えば、ある時刻にアイテム1,2,3を同時に買った場合、h1 + h2 + h3 に加えて|h1 - h2| + |h2 - h3| だけあなたの強さが増加します。
あなたは、全てのイベントを攻略した後の所持金を最大化したいと考えています。
アイテムの情報とイベントの情報を入力とし、すべてのイベントを攻略した後の所持金の最大値を出力するプログラムを作成せよ。
入力
入力は以下の形式で与えられる。
N M v1 h1 v2 h2 : vN hN t1 s1 t2 s2 : tM sM
1行目にアイテムの数 N (1 ≤ N ≤ 3000) とイベントの数 M (1 ≤ M ≤ 1000) が与えられる。続く N 行にアイテム i の値段
出力
所持金の最大値を1行に出力する。ただし、攻略することができない場合には「-1」を出力する。
入出力例
入力例 1
5 4 3 3 2 1 1 5 4 2 2 6 4 1 8 2 10 4 12 17
出力例 1
2
入力例 2
5 4 3 3 2 1 1 5 4 2 2 6 4 1 8 2 10 4 12 30
出力例 2
-1