Problem Description

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$.

Input Format

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 Format

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.

4 14 3
1 1 1
1 2 1
1 3 1
2 1 1
2 2 3
2 3 3
2 4 2
3 1 1
3 2 3
3 3 3
3 4 2
4 2 2
4 3 2
4 4 2

3

3 1 2
1 1 1

-1

4 5 1
1 1 5
2 2 -3
2 3 -4
3 3 1
4 4 2

15

Hint

[Sample 1 Explanation]:

The given matrix is:

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.

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:

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.

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