0166 - 地震予測

時間制限 1 秒 / メモリ制限 64 MB / 得点 1 / Writer ei1439 / x 6 / 統計 /


TLE
1sec
MLE
64MB
得点
1

問題


20XX年、技術の進歩により地震の予測が可能になった今、KOMONO国KOMONO市KOMONO町にとって過去最悪の問題が発生した。

KOMONO町長のこものによると、昨日の夜日課の素振りをしていた時、NASAからメールが来たそうだ。

その内容は、大きな地震が連続してKOMONO町敷地内で発生する、というものである。

実は高層建築物マニアであるこものは、超焦った。

今ある建築物達がどれだけ崩壊してしまうのだろうと危惧したこものは、この町最高の技術を持つあなたに、国家機密である地震の震源地と震度、それから今ある高層建築物の耐久力を教えるので、建物物がいくつ崩壊せずに残るのかを予測をするプログラムを作って欲しいと懇願してきた。

町の仲間たちや町長こものの為にも、プログラムを作って欲しい。

詳細

町の地形について

KOMONO町はこものの趣味により、下図のように町の形がマス目状になっている。



マス目は左上(1,1)〜右下(w,h)の座標が割り当てられている。

地震のゆれの伝わり方について

地震のゆれは震源地を中心に広がっていく。
ゆれの大きさは1マス広がっていくごとに1減少していく。
下図は、(3,3)の位置に震度3の地震が発生したときの例である。
黒い数字はその場所での震度(ゆれの大きさ)を表している。



建物の耐久力と地震のゆれについて

建物の耐久力はその場所でのゆれの大きさ分減少してしまう。
建物の耐久力が0未満になると、その建物は崩壊する(耐久力0の建物は建ったままである)。
例えば上図の(2,2)の場所に耐久力3の建物があった時に上の例の地震が来たら、その建物の残りの耐久力は1になるが、建ったままである。
(3,3)の場所に耐久力2の建物があった時に上の例の地震が来たら、その建物の耐久力は-1になり、0未満なので崩壊してしまう。

入力

w h
n
x1 y1 s1
x2 y2 s2
.
.
.
xn yn sn
m
i1 j1 p1
i2 j2 p2
.
.
.
im jm pm

w, h:町の横の長さw、横の長さh
n:建物の数
x, y, s:建物の座標(x,y)と耐久力s
m:地震の数
i, j, p:震源の座標(i,j)と震度p

出力

崩壊せずに建っている建物の数を出力する。
ただし、建物が一つも残っていない場合は、oh...と出力する。

制約

0 < w <= 1000, 0 < h <= 1000
0 < n <= 3000, 0 < m <= 500
0 < x <= w, 0 < y <= h
0 < s <= 1000, 0 < p <= 300

入力例1

6 6
5
5 1 10
2 2 4
6 3 5
4 4 3
2 6 1
3
4 2 5
2 4 3
5 6 4


下図は入力例1の建物と震源地を表した地図である。
□が建物で、数字は耐久力を表す。
○が震源地で、数字は震度を表す。



出力例1

3


入力例2

4 5
5
4 1 8
1 2 10
3 4 5
1 5 6
4 5 2
2
3 2 10
2 4 5


出力例2

oh...