You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

现在，问题升级了，小红有一个 $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$ 。