题目描述

给定一个 $n \times n$ 的矩阵，你可以进行若干次操作。

每次操作，你可以将一个 $k \times k$ 的 连续 子矩阵里的所有数全都加上 $1$ 或者全都减去 $1$。

初始时，矩阵中有 $m$ 个位置上的数不为 $0$，其它位置上的数均为 $0$。

请你求出至少需要多少次操作，可以将矩形中所有数都变为 $0$。

输入格式

第一行三个整数 $n,m,k$，分别表示矩阵大小，非 $0$ 格数和每次修改的连续子矩阵大小。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示初始时矩阵的第 $x$ 行第 $y$ 列上的数为 $z$。

输出格式

一行一个整数，表示最少操作次数。

特别地，如果无法使矩阵中所有数都变为 $0$，输出 -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

提示

【样例 1 解释】:

给出的矩阵为：

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

具体步骤：

先将以第一行第一列为左上角的连续子矩阵执行 减 1 操作 一次；

再将以第二行第二列为左上角的连续子矩阵执行 减 1 操作 两次。

总共三次。

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

【样例 2 解释】：

给出的矩阵为：

1 0 0
0 0 0
0 0 0

只通过 $2\times 2$ 的连续子矩阵操作不可能使得所有格子上的数都变为 $0$。

【数据范围】

本题采用捆绑测试。

对于所有数据，$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$，每对 $(x,y)$ 至多出现一次，$1 \le |z| \leq 10^9$。

数据保证如果有解，答案不超过 $2^{63}-1$。

【提示】

本题读入量较大，建议使用较快的读入方式。