P6070 『MdOI R1』Decrease

给定一个 $n \times n$ 的矩阵，你可以进行若干次操作。 每次操作，你可以将一个 $k \times k$ 的 **连续** 子矩阵里的所有数全都加上 $1$ 或者全都减去 $1$。 初始时，矩阵中有 $m$ 个位置上的数不为 $0$，其它位置上的数均为 $0$。 请你求出至少需要多少次操作，可以将矩形中所有数都变为 $0$。

无

无

【样例 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$。 --- 【提示】 本题读入量较大，建议使用较快的读入方式。