AOJ 7632 - Soldier

Soldier

Time Limit: 5000ms

Memory Limit: 65536KB

This problem will be judged on PKU. Original ID: 3248
64-bit integer IO format: %lld Java class name: Main

Submit Status Statistics

Font Size:

Description

There are k soldiers placed on an n-row and m-column chessboard. It is allowed that more than one soldier are placed on the same grid.

If the Manhattan distance between a grid(in ath row and bth column) and a soldier(in xth row and yth column), |x-a|+|y-b|, is not larger than the control range of that soldier, then the grid will be controlled.

Could you tell the total number of all the controlled grids?

Input

The input contains only one case.
The input begins with three positive integers, n, m and k, indicating the length of row and column, and the number of soldiers.
In the next k lines each line contains three non-negative integers, x, y, r, indicating a soldier is placed on the xth row and yth column, and the control range of that soldier is r.
It is guaranteed that 1 ≤ n, m ≤ 100000000，1 ≤ k ≤ 100000

Output

Print the total number of all the controlled grids.

Sample Input

Sample Output

Source

POJ Monthly--2007.07.08, Chen, Qifeng