题目描述

先前，小红有一个数组，要求这个数组中选择若干个数，使得选出的数之和与剩下的数之和的差值绝对值尽可能小。

现在，问题升级了，小红有一个 $n\times m$ 的矩阵，要求从这个矩阵中选择出一个正方形，使得正方形中的数之和与剩下的数之和的差值绝对值尽可能小。

你能帮帮小红吗？

输入描述

第一行，两个正整数 $n$ 和 $m(1\leq n,m\leq 1000)$ ，表示矩阵的行数和列数

接下来的 $n$ 行，每行有 $m$ 个正整数，第 $i$ 行的第 $j$ 个正整数为 $a_{i,j}(1\leq a_{i,j}\leq 10000)$

输出描述

一个整数，表示正方形中的数之和与剩下的数之和的差值绝对值的最小值。

样例

输入

3 3
9 9 8 
2 4 4
3 5 3

输出

1

说明

选择 a[1][1], a[1][2], a[2][1], a[2][2] 构成的长度为 $2$ 的正方形，这些数和为 $24$ ，剩下的数和为 $23$ ，此时差值绝对值最小，为 $1$ 。

思路：二维前缀和+二分

这个问题其实就是在求一个靠近 $\frac{sum}{2}$ 的最近的数，不过这个数是由正方形中的数的和组成的。

那么可以考虑枚举正方形的左上角端点，然后二分正方形的边长，找到一个正方形数之和大于等于 $\frac{sum}{2}$ 的最小边长。

而这里判断时需要快速求出一个正方形内数的和，可以通过预处理二维前缀和，然后查询可以$O(1)$计算出。

时间复杂度：$O(nmlogn)$