B21 实践-5 部落放置

题目描述 玉春的神准备捏造两个部落，令其分布在一个 $n\times m$ 的棋盘世界中。 棋盘世界的地下蕴藏着神秘力量，都存储在原石中，每个格子都有可能存在原石，玉春的神预知了每一个格子的原石能量值 $v$。 每个部落都是一个 $x \times x$ 大小的矩阵。 请问如何放置这两个部落，才能使得他们之间的竞争力更接近（框选的原石的能量值最接近）。 放置要求： 1 两个部落必须完全独立，不可以共用地盘； 2 部落的边界不得越过棋盘世界； 3 要求两个部落内存储的原石能量和的差值最小。

输入格式 共 $n+2$ 行： 第一行两个正整数 $n,m$ ，分别表示棋盘世界的行、列数； 接下来的 $n$ 行，每行 $m$ 个正整数，描述该矩阵地下蕴藏的原石能量值； 接下来一行一个整数$x$，表示每个部落的边长。

输出格式 一个整数，表示两个部落的原石能量值的差值。

样例输入

5 5
1 1 1 0 0
1 1 1 1 1
0 0 0 1 1
0 0 1 1 1
0 0 0 0 1
2

样例输出

0

样例解释 如题样例：棋盘世界是 $5 \times 5$ 的世界 ，有多个差值最小的选取方法，其中一个方法为： 第一个部落框在 $(1,1)$ -> $(2,2)$； 第二个部落框在 $(2,4)$ -> $(3,5)$ 。

数据范围 对于 $30\%$ 的数据： $1 \le x \le n,m \le 10$，$1\le v \le 100$ ; 对于 $100\%$ 的数据： $1 \le x \le n,m \le 80$，$1 \le v \le 10^{10}$ 。