問題
一周の距離が $D$ の円形の池があり、その周りに野原が広がっています。
一匹の野うさぎが池の北端の位置にいます。
$N$ 個の地点には牧草が生えています。
$i$ $(1 \leq i \leq N)$ 個目の牧草は池の北端から時計周りに距離 $P_i$ 進んだ位置にあり、おいしさは $V_i$ です。
野うさぎはこれから $M$ 回にわたって移動を行います。
$i$ $(1 \leq i \leq M)$ 回目の移動では、現在地点を除いた、現在地点からの距離が $A_i$ 以下の任意の地点に一度跳ねることによって移動します。
野うさぎは各移動の後で、その地点に牧草が生えていた場合その牧草を食べることができます。
どの牧草もなくなることはありません。
野うさぎはおいしさ $X$ の牧草を食べると、幸福度が $X$ 増加します。
考えうる野うさぎの幸福度の増加量の最大値を求めてください。
制約
- $2 \leq D \leq 2,000$
- $1 \leq N \leq D - 1$
- $1 \leq M \leq 1,000$
- $1 \leq P_i \leq D - 1$ $(1 \leq i \leq N)$
- $P_i \neq P_j$ $(i \neq j)$
- $1 \leq V_i \leq 10^9$ $(1 \leq i \leq N)$
- $1 \leq A_i \leq D - 1$ $(1 \leq i \leq M)$
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
$D$ $N$ $M$ $P_1$ $V_1$ $P_2$ $V_2$ $\vdots$ $P_N$ $V_N$ $A_1$ $A_2$ $\vdots$ $A_M$
出力
考えうる野うさぎの幸福度の増加量の最大値を出力せよ。
出力の末尾には改行を入れること。
入出力例
入力例１
11 4 3 3 1 6 3 2 3 9 4 3 1 4
出力例１
8
以下のように移動することで最大値 $8$ を得ることができます。 池の北端から時計回りに距離 $p$ 進んだ位置を、地点 $p$ と表します。
- 地点 $0$ から地点 $3$ に移動する。地点 $3$ に生えているおいしさ $1$ の牧草を食べて幸福度が $1$ 増加する。
- 地点 $3$ から地点 $2$ に移動する。地点 $2$ に生えているおいしさ $3$ の牧草を食べて幸福度が $3$ 増加する。
- 地点 $2$ から地点 $9$ に移動する。地点 $9$ に生えているおいしさ $4$ の牧草を食べて幸福度が $4$ 増加する。
入力例２
20 5 7 4 84 19 73 1 67 3 15 12 98 2 5 9 6 7 8 1
出力例２
494