問題
横$ W $枚、縦$ H $枚の$ W \times H $枚のタイルがあり、左から$ x $列目、上から$ y $行目のタイルを$(x, y)$と表します。
※以降、$(1 \leqq x \leqq W)$，$(1 \leqq y \leqq H)$を満たすタイルを存在するタイルと呼びます。
最初、全てのタイルが白色です。
$ N $回にわたって整数$a_{i}, b_{i}, l_{i}$が与えられます。これは、$( a_{i} - l_{i} \leqq x \leqq a_{i} + l_{i})$，$( b_{i} - l_{i} \leqq y \leqq b_{i} + l_{i})$を満たすすべての存在するタイルが赤く塗られていることを示します。
このタイル上には$ M $個のお宝があり、お宝$ j $は$(o_{j}, p_{j})$にあり、取ると$v_{j}$の価値を得られます。
任意の赤いタイル上にいるあなたは、周囲$8$マスにある赤い存在するタイルに好きな回数だけ移動できます。
※$(x, y)$にいるときに行けるタイルは、
$(x, y+1)$，$(x, y-1)$，$(x+1, y)$，$(x-1, y)$，$(x-1, y+1)$，$(x+1, y+1)$，$(x-1, y-1)$，$(x+1, y-1)$
の$8$つです。
同じタイル上を複数回移動できますが、お宝$ j $は初めにそのタイルの上に乗ったときの一回のみ取ることができます。
この条件で得られる価値の合計の最大値を求めてください。
入力
入力は以下の形式で標準入力から与えられます。
$W$ $H$
$N$
$a_{1}$ $b_{1}$ $l_{1}$
$a_{2}$ $b_{2}$ $l_{2}$
$\cdots$
$a_{N}$ $b_{N}$ $l_{N}$
$M$
$o_{1}$ $p_{1}$ $v_{1}$
$o_{2}$ $p_{2}$ $v_{2}$
$\cdots$
$o_{M}$ $p_{M}$ $v_{M}$
出力
得られる価値の合計の最大値を出力してください。また、出力の最後に改行を入れてください。
制約
全ての入出力ケースについて以下を満たします。
- $1 \leqq W, H \leqq 10^{9}$
- $1 \leqq N, M \leqq 3000$
- $1 \leqq a_{i} \leqq W$, $1 \leqq b_{i} \leqq H$, $0 \leqq l_{i} \leqq \max(H, W) $ $(1 \leqq i \leqq N)$
- $1 \leqq o_{j} \leqq W$, $1 \leqq p_{j} \leqq H$, $1 \leqq |v_{j}| \leqq 10^{9}$ $(1 \leqq j \leqq M)$
- 入力はすべて整数である
入出力例
入力例1
5 4 2 2 2 1 4 2 0 3 2 2 3 4 2 2 4 4 1
出力例1
5
$(1, 1)$にいるとします。このとき$(1, 1) \to (1, 2) \to (2, 2)$と移動し、お宝$ 1 $を取って価値$ 3 $を得ます。続いて$(2, 2) \to (3, 2) \to (4, 2)$ と移動し、お宝$ 2 $を取って価値$ 2 $を得ます。これ以上価値の合計を大きくすることはできないので、最初に$(1, 1)$にいた場合に得られる価値の合計の最大値は$ 5 $となります。他にも得られる価値の合計が$ 5 $になるような開始位置は存在しますが、これを超える価値の合計を得られる事はありません。よって、得られる価値の合計の最大値は$5$です。
入力例2
5 4 2 2 2 1 4 2 0 3 2 2 -3 4 2 2 4 4 1
出力例2
2
入力例1とほとんど同じですがお宝$ 1 $の価値が$ -3 $になっています。この場合、得られる価値の合計の最大値は$ 2 $です。
入力例3
4 1 4 4 1 3 2 1 2 1 1 4 2 1 0 2 2 1 5 3 1 9
出力例3
14