Baku 将一块正方形的土地均匀地划分成了 $N \times N$ 个小正方形田地。在每块田地里播种 $P$ 颗种子后，一周后观察发现，有些种子长成了新芽，而有些则没有。例如，下图展示了在 $6 \times 6$ 的田地中，每块田地播种 3 颗种子后长出新芽的情况。最左上角的田地长出了 2 个新芽，最右下角的田地长出了 1 个新芽。

在巡视田地时，Baku 想到了最近学到的中位数（median）。中位数是奇数个给定值中的一个，即当给定值排序后，恰好位于中间的值。例如，如果给定的五个值为 0, 1, 2, 2, 3，则中位数为 2。

Baku 对中位数和平均值之间的差异感到好奇，因此他想比较每块田地中新芽数量的中位数和平均值。为了观察各种情况，我们将针对正方形形状的相邻 $K \times K$ 个田地区域来计算中位数和平均值。这样，在给定的 $N \times N$ 个田地中，总共可以进行 $(N - K + 1) \times (N - K + 1)$ 次比较。

例如，对于上图中的田地，以 $3 \times 3$ 为单位计算所有中位数和平均值，结果如下表所示。最左上角的 $3 \times 3$ 个田地中新芽的数量分别为 2, 1, 0, 0, 1, 0, 2, 0, 1，因此中位数为 1，平均值为 $7/9$。最右上角的 $3 \times 3$ 个田地对应的中位数为 0，平均值为 $8/9$。

Baku 想要找出中位数和平均值之差的最大值。在上面的例子中，最大值出现在下图中红色正方形标记的部分，其中中位数为 0，平均值为 1，两者的差为 1。

为了计算方便，Baku 想要找出中位数与平均值之差乘以 $K^2$ 后的最大值。因此，在上面的例子中，最大值为 9。你需要为 Baku 实现以下函数。

int diff(int K, int[][] V)：这是一个仅被调用一次的函数。$V$ 是一个大小为 $N \times N$ 的数组（vector）。每块田地中新芽的数量 $V[0..N-1][0..N-1]$ 作为参数给出。请计算并返回以 $K \times K$ 大小为单位计算出的中位数与平均值之差乘以 $K^2$ 后的最大值。

实现细节

你需要提交一个名为 sprout.cpp 的文件。该文件必须实现以下函数：

int diff(int K, int[][] V)

该函数应按上述说明运行。当然，你可以创建其他函数并在内部使用它们。提交的代码不得执行输入输出操作或访问其他文件。

Grader 示例

提供的 grader 按以下格式读取输入：

• 第 1 行：$N \ K$ ($N$: 田地大小，$K$: 区域大小)
• 第 $2+i$ 行 ($0 \le i \le N-1$)：$V_{i0} \ V_{i1} \ \dots \ V_{i,N-1}$ ($V_{i0}, V_{i1}, \dots, V_{i,N-1}$: 第 $i$ 行新芽的数量)

提供的 grader 会输出你的代码在 diff() 函数中返回的值。

数据范围

• $1 \le N \le 2,000$
• $K$ 为奇数，且 $1 \le K \le N$
• $0 \le V_{ij} \le 30$ ($0 \le i, j \le N-1$)

子任务

• 子任务 1 [17 分]：$N \le 100$
• 子任务 2 [24 分]：$N \le 300$
• 子任务 3 [42 分]：$N \le 700$
• 子任务 4 [67 分]：无额外限制。

样例

输入样例 1

6 3
2 1 0 1 0 2
0 1 0 3 0 0
2 0 1 0 0 2
1 2 2 2 2 0
1 2 2 0 0 1
0 1 0 0 2 1

输出样例 1

9

输入样例 2

4 3
10 20 10 20
20 10 20 10
10 20 10 20
20 10 20 10

输出样例 2

40

Figure 1. 在 6 × 6 的田地中，每块田地播种 3 颗种子后长出新芽的情况。