Problem Description

Given an $n \times n$ matrix, you can perform several operations.

Each operation allows you to add or subtract 1 from all numbers in a continuous $k \times k$ submatrix.

Initially, there are $m$ positions in the matrix that are non-zero, while all other positions are zero.

You need to determine the minimum number of operations required to make all numbers in the matrix zero.

Input Format

The first line contains three integers $n, m, k$, representing the size of the matrix, the number of non-zero cells, and the size of the continuous submatrix for each modification.

The next $m$ lines each contain three integers $x, y, z$, indicating that the number in the $x$-th row and $y$-th column of the initial matrix is $z$.

Output Format

Output a single integer representing the minimum number of operations.

If it is impossible to make all numbers in the matrix zero, output -1.

Sample Input and Output

Sample Input #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

Sample Output #1

3

Sample Input #2

3 1 2
1 1 1

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

15

Notes

Sample 1 Explanation:

The given matrix is:

1 1 1 0
1 3 3 2
1 3 3 2
0 2 2 2

Steps:

1. Perform a subtract 1 operation on the continuous submatrix with the top-left corner at the first row and first column.
2. Perform a subtract 1 operation twice on the continuous submatrix with the top-left corner at the second row and second column.

Total: Three operations.

Sample 2 Explanation:

The given matrix is:

1 0 0
0 0 0
0 0 0

It is impossible to make all cells zero using only $2 \times 2$ continuous submatrix operations.

Data Range:

This problem uses subtask testing.

For all data, $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, $1 \leq |z| \leq 10^9$.

The data guarantees that if there is a solution, the answer will not exceed $2^{63} - 1$.

Hints:

This problem has a large input size, so it is recommended to use fast input methods.

见题面 Input 部分

见题面 Output 部分