题目描述

猪猪大仙准备捏造两个部落，令其分布在一个 $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}$ 。