010 - ゲームの攻略

問題

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

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

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

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

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

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

入力

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

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

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

出力

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