Minimum Operations to Zero Matrix

Given an $n \times n$ matrix, initially with all zeros except for $m$ cells which contain non-zero integers, you are allowed to perform the following operation any number of times:

In one operation, you can choose any $k \times k$ contiguous submatrix and either add $1$ to all its cells or subtract $1$ from all its cells.

Determine the minimum number of operations required to turn the entire matrix into zeros. If it is impossible, output -1.

Note: The matrix indices are 1-indexed, and only $m$ positions are non-zero initially, with their values provided. The remaining positions contain $0$.

inputFormat

The first line contains three integers $n$, $k$, and $m$, where $n$ is the size of the matrix, $k$ is the size of the submatrix for each operation, and $m$ is the number of cells with nonzero values.

Each of the next $m$ lines contains three integers $r$, $c$, and $a$, representing that the cell at row $r$ and column $c$ has the initial value $a$. It is guaranteed that the rest of the matrix cells are $0$.

It is guaranteed that $1 \le r, c \le n$.

outputFormat

Output a single integer: the minimum number of operations required to make the matrix all zeros, or -1 if it is impossible.

sample

4 2 7
1 1 3
1 2 3
2 1 3
2 2 1
2 3 -2
3 2 -2
3 3 -2

5