Pyramid(貫きピラミッド) - joi2009-day1

時間制限: 5秒

メモリ制限: 64MB

古代JOI王国では, 国王の墓として砂漠にピラミッドを作る風習があった. この国では, 国王が死ぬと, 占いによって決められる「ある場所」に, 占いによって決められる「ある高さ」のピラミッドを作ることになっている.

JOI王国の砂漠は東西幅がW, 南北幅がHの長方形の形をしている. 砂漠は1×1の正方形の区画に分かれており, 各区画は0 ≤ x < W, 0 ≤ y < H を満たす整数x,y によって(x,y)と表現される. 区画(0,0)は北西隅の区画であり, 区画(x,y)は, 区画(0,0)から東にx, 南にy 進んだ地点に位置する区画である.

さて, ピラミッドは次のようにして作られる. まず, 占いによってピラミッドの中心の区画(X,Y)と高さhが決められる. それに従って, 次の規則で砂漠内の各区画に石を積むことによってピラミッドを建設する:

区画(X,Y)を中心とする高さhのピラミッドを作る場合, 砂漠内の区画(x,y)にはmax{0, h − max{|X − x|, |Y − y|}} 個の石を積む. 砂漠の外には石は一切積まない.

たとえば, 砂漠の大きさがW = 7, H = 6 であり, 区画(2,1)を中心とする高さ3のピラミッドを作った場合, 各区画に積まれている石の数は以下のようになる.

しかし, JOI王国はそれほど広くはないため, ピラミッドは過去のピラミッドと「重なって」作られることもある. すなわち, 新たにピラミッドを作ろうとしてある区画にn個の石を積むことになった場合に, その区画に既にn 個以上の石が積まれていた場合は, その区画には何もしない. 一方, その区画にまだn個未満しか石が積まれていなかった場合は, その区画に積まれている石の数をn個まで増やす.

そのため, 多数のピラミッドが作られた末の見た目は複雑となる. たとえば上図の状態で, さらに区画(4,3)を中心とする高さ4のピラミッドを作ると, 各区画に積まれている石の数は以下のようになる.

さて, 考古学者であるあなたは, 一体どれほどの数の石がピラミッドの建設に用いられているかを知りたくなった.

全てのピラミッドの中心位置の区画と高さが与えられた時, それらを建設するのに必要な石の数を求めるプログラムを書け.

Input.

入力ファイルpyramid.inの1行目は3つの整数W,H,N (1 ≤ W,H ≤ 3000, 1 ≤ N ≤ 10 000) が書かれている. W,H はそれぞれ砂漠の横幅,縦幅を表す. また, Nはピラミッドの個数を表す.

2行目以降のi+1行目(1 ≤ i ≤ N)には, 3つの整数x[i], y[i], h[i] (0 ≤ x[i] < W, 0 ≤ y[i] < H, 1 ≤ h[i] < 3000) が書かれている. これらは, i 番目のピラミッドの中心位置の区画が(x[i],y[i])であり, 高さがh[i]であることを表す.

Output.

出力は, 標準出力に行うこと. 全てのピラミッドを建設するのに必要な石の数を表す1つの整数を出力せよ.

採点基準

採点用データのうち, 配点の10% 分については, W,H ≤ 1000, N ≤ 5 を満たす. また, 配点の25% 分については, W,H ≤ 500 かつ, 全てのピラミッドの高さが100以下である.

例1

pyramid.in	標準出力
`7 6 2 2 1 3 4 3 4`	`81`

例2

pyramid.in	標準出力
`3000 3000 1 1500 1500 3000`	`17999999500`