시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 1024 MB24161466.667%

문제

古代 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 のピラミッドを作ると,各区画に積まれている石の数は以下 のようになる.

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

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

입력

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

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

출력

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

예제 입력 1

7 6 2
2 1 3
4 3 4

예제 출력 1

81

예제 입력 2

3000 3000 1
1500 1500 3000

예제 출력 2

17999999500