Communication Stations

Time limit1.5sMemory limit1024 MB

Summary

Count the lattice points in an N by M map that lie within Manhattan distance p_i of at least one of K stations.

Level: Medium6 of 10
Topics: Prefix sum, Geometry, Implementation
Solved: No attempts yet

Problem

The Republic of Korea Air Force installed communication stations at several locations so that it could communicate smoothly with fighter jets in flight and with ground units. So far, $K$ stations have been placed. Station $i$ sits at $(y_i, x_i)$ and emits a signal with strength $p_i$ . Any fighter jet at an integer lattice point $(y, x)$ that satisfies $|y_i - y| + |x_i - x| \leq p_i$ can communicate with that station. When signals from different stations overlap, each keeps its original strength.

Given the map height $N$ , the map width $M$ , and the positions and strengths of the $K$ stations, count the integer lattice points $(y, x)$ inside the map where a fighter jet can communicate with at least one station.

Input

The first line contains three integers $N$ , $M$ , and $K$ , separated by spaces. ( $1 \leq N, M \leq 3000$ , $1 \leq K \leq 300000$ )

From line 2 to line $K+1$ , each line contains three integers $y_i$ , $x_i$ , and $p_i$ , separated by spaces, which are the row position, column position, and signal strength of station $i$ . ( $1 \leq y_i \leq N$ , $1 \leq x_i \leq M$ , $1 \leq p_i \leq 3000$ )

No two stations share the same position.

Output

Print the number of integer lattice points inside the map where a fighter jet can communicate with at least one station.

Examples1

Example 1
Input
```
6 7 4
2 6 2
3 3 1
6 1 3
5 6 2
```
Expected output
```
35
```