P7316 [COCI 2018/2019 #3] NLO

You are given an $N \times M$ rectangular wheat field. Each cell of the field has some amount of grass. Initially, the amount of grass in every cell is $1$. Over $K$ days, circular UFOs will land on the field and draw circles. On the morning of day $i$, a UFO with radius $R_i$ lands on cell $(X_i, Y_i)$, and all cells within distance $R_i$ from that cell will be affected. If a cell $(x, y)$ is affected, i.e. $(X_i-x)^2+(Y_i-y)^2 \le R_i^2$, then the amount of grass in that cell becomes $0$. When a new day arrives, the amount of grass in every cell increases by $1$. Find the sum of grass over all cells on the evening of day $K$.

The first line contains positive integers $N, M$, representing the size of the field. The second line contains a positive integer $K$, representing the number of days. The next $K$ lines each contain positive integers $X_i, Y_i, R_i$, describing the landing cell and the radius of the UFO.

Output the total amount of grass.

#### Explanation of Sample 1 The field on the evening of day 1: |$1$|$1$|$1$|$1$|$1$|$1$| | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | |$1$|$1$|$1$|$\red 0$|$1$|$1$| |$1$|$1$|$\red 0$|$\red 0$|$\red 0$|$1$| |$1$|$\red 0$|$\red 0$|$\red 0$|$\red 0$|$\red 0$| |$1$|$1$|$\red 0$|$\red 0$|$\red 0$|$1$| |$1$|$1$|$1$|$\red 0$|$1$|$1$| The field on the evening of day 2: |$2$|$2$|$\red 0$|$2$|$2$|$2$| | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | |$2$|$\red 0$|$\red 0$|$\red 0$|$2$|$2$| |$\red 0$|$\red 0$|$\red 0$|$\red 0$|$\red 0$|$2$| |$2$|$\red 0$|$\red 0$|$\red 0$|$1$|$1$| |$2$|$2$|$\red 0$|$1$|$1$|$2$| |$2$|$2$|$2$|$1$|$2$|$2$| The field on the evening of day 3: |$3$|$3$|$1$|$\red 0$|$3$|$3$| | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | |$3$|$1$|$\red 0$|$\red 0$|$\red 0$|$3$| |$1$|$1$|$1$|$\red 0$|$1$|$3$| |$3$|$1$|$1$|$1$|$2$|$2$| |$3$|$3$|$1$|$2$|$2$|$3$| |$3$|$3$|$3$|$2$|$3$|$3$| Therefore, the total amount of grass is $68$ units. #### Constraints For $20\%$ of the testdata, $N, M \le 1000$. For $100\%$ of the testdata, $1 \le N, M \le 10^5$, $1 \le K \le 100$, $1 \lt X_i \lt N$, $1 \lt Y_i \lt M$, $1 \le R_i \le \min(X_i-1, Y_i-1, N-X_i, M-Y_i)$. #### Note **The score of this problem follows the original COCI settings, with a full score of $110$.** **This problem is translated from [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #3](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf) _T4 NLO_.** Translated by ChatGPT 5