0747 - ゲームの攻略

時間制限 2 秒 / メモリ制限 256 MB / 得点 20 / Writer root / x 9 / 統計 /

TLE
2sec
MLE
256MB
得点
20

問題

あなたは所属するプログラミング部の部室から古びたボードゲームを発見しました。面白そうなので遊んでみることにしました。

このゲームは M 個のイベントから成り、時刻 ti にイベント i を攻略しなければいけません。ただし、そのときにあなたの強さは si 以上である必要があり、si 以上にできない場合はゲームオーバーになります。ゲーム開始時（時刻０）のあなたの強さは０ですが、アイテムを買うことで強さを増加させることができます。ゲーム開始時のあなたの所持金は０ですが、１単位時間あたり１増加します。

ボードにはそれぞれ１から N の番号が付けられた N 個のアイテムが順番に並べられており、アイテム i の値段は vi で、それを購入するとあなたの強さが hi 増加します。アイテムは所持金が十分であれば好きな時刻に好きな数だけ購入することができますが、残っているアイテムの中で番号が小さいものから順に選ばなければなりません。各アイテムは１度購入すると消滅します。

また、同じ時刻に複数のアイテムを連続で買うことができ、このとき隣り合うアイテムの hi の差分の和をボーナスとして得ることができます。例えば、ある時刻にアイテム１,２,３を同時に買った場合、h1 + h2 + h3 に加えて|h1 - h2| + |h2 - h3| だけあなたの強さが増加します。

あなたは、全てのイベントを攻略した後の所持金を最大化したいと考えています。

アイテムの情報とイベントの情報を入力とし、すべてのイベントを攻略した後の所持金の最大値を出力するプログラムを作成せよ。

入力

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

N M
v1 h1
v2 h2
:
vN hN
t1 s1
t2 s2
:
tM sM

１行目にアイテムの数 N (1 ≤ N ≤ 3000) とイベントの数 M (1 ≤ M ≤ 1000) が与えられる。続く N 行にアイテム i の値段 vi と強さの増加量 hi (1 ≤ vi, hi ≤ 100000) が与えられる。続く M 行にイベント i の時刻 ti と条件 si (1 ≤ ti, si ≤ 100000) が与えられる。ただし、i < j のとき、ti < tj とする。入力はすべて整数で与えられる。

出力

所持金の最大値を１行に出力する。ただし、攻略することができない場合には「-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