『MdOI R1』Decrease

给定一个 $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 解释】: 给出的矩阵为： ```plain 1 1 1 0 1 3 3 2 1 3 3 2 0 2 2 2 ``` 具体步骤： 先将以第一行第一列为左上角的连续子矩阵执行 **减 1 操作** 一次； 再将以第二行第二列为左上角的连续子矩阵执行 **减 1 操作** 两次。 总共三次。 ```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 ``` 【样例 2 解释】： 给出的矩阵为： ```plain 1 0 0 0 0 0 0 0 0 ``` 只通过 $2\times 2$ 的连续子矩阵操作不可能使得所有格子上的数都变为 $0$。 【数据范围】 **本题采用捆绑测试。** | 子任务编号 | $n\leq$ | $k\leq$ | 分值 | | :--------: | :------------: | :-----: | :--: | | 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 | 对于所有数据，$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$。 --- 【提示】 本题读入量较大，建议使用较快的读入方式。