P6070 "MdOI R1" Decrease

Given an $n \times n$ matrix, you may perform several operations. In each operation, you can add $1$ to all numbers in a **contiguous** $k \times k$ submatrix, or subtract $1$ from all numbers in a **contiguous** $k \times k$ submatrix. Initially, there are $m$ positions in the matrix whose values are non-zero, and all other positions are $0$. Please find the minimum number of operations required to make all numbers in the matrix become $0$.

The first line contains three integers $n,m,k$, representing the matrix size, the number of non-zero cells, and the size of the contiguous submatrix modified in each operation. The next $m$ lines each contain three integers $x,y,z$, meaning that initially the value at row $x$, column $y$ of the matrix is $z$.

Output one integer in a single line, representing the minimum number of operations. In particular, if it is impossible to make all numbers in the matrix become $0$, output `-1`.

[Sample 1 Explanation]: The given matrix is: ```plain 1 1 1 0 1 3 3 2 1 3 3 2 0 2 2 2 ``` Steps: First, perform the **subtract 1 operation** once on the contiguous submatrix whose top-left corner is at row 1, column 1. Then, perform the **subtract 1 operation** twice on the contiguous submatrix whose top-left corner is at row 2, column 2. In total, 3 operations. ```plain 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 3 2 0 2 2 2 0 1 1 1 0 0 0 0 1 3 3 2 0 2 2 2 0 1 1 1 0 0 0 0 0 2 2 2 0 2 2 2 0 1 1 1 0 0 0 0 ``` [Sample 2 Explanation]: The given matrix is: ```plain 1 0 0 0 0 0 0 0 0 ``` It is impossible to make all cells become $0$ using only operations on contiguous $2\times 2$ submatrices. [Constraints] **This problem uses bundled testdata.** | Subtask ID | $n\leq$ | $k\leq$ | Score | | :--------: | :------------: | :-----: | :---: | | 1 | $10^3$ | $1$ | 11 | | 2 | $20$ | $20$ | 14 | | 3 | $100$ | $100$ | 17 | | 4 | $10^3$ | $10^3$ | 34 | | 5 | $5\times 10^3$ | $10^3$ | 24 | For all testdata, $1\leq n\leq 5\times 10^3$, $1\leq m\leq \min(n^2,5\times 10^5)$, $1\leq k\leq \min(n,10^3)$, $1\leq x,y\leq n$, each pair $(x,y)$ appears at most once, and $1 \le |z| \leq 10^9$. The testdata guarantees that if a solution exists, the answer does not exceed $2^{63}-1$. --- [Hint] The input size is large, so it is recommended to use a faster input method. Translated by ChatGPT 5