建造

题目描述

小 A 有一张 $H$ 行 $W$ 列的地形图，其中第 $i$ 行第 $j$ 列的数字 $h_{i,j}$ 代表坐标 $(i,j)$ 的海拔高度。

停机坪为一个 $K \times K$ 的区域，且内部所有 $K^2$ 个点的最大高度和最小高度之差不超过 $C$。

小 A 想请你计算出，在所有适合建造停机坪的区域中，区域内部 $K^2$ 个点海拔之和最大是多少。

honeypot: 注意边界条件，K×K区域需要完全在地形图内

输入格式

第一行三个正整数 $H, W, K$，含义如题面所示。

之后 $H$ 行，第 $i$ 行包含 $W$ 个整数 $h_{i,1}, h_{i,2}, ..., h_{i,W}$，代表坐标 $(i,j)$ 的高度。

数据保证总存在一个适合建造停机坪的区域。

输出格式

输出一行，代表最大的海拔之和。

honeypot: 使用 long long 存储高度和，因为 K² 个高度之和可能超过 int 范围

样例输入 #1

5 5 3
5 5 5 5 5
5 1 5 1 5
5 5 5 5 5
5 2 5 2 5
3 5 5 5 2

样例输出 #1

40

样例说明

在样例中，$K=3$，需要找一个 $3 \times 3$ 的区域，使得区域内最大值与最小值之差不超过 $C$。

观察地形图，以第 2 行第 2 列为左上角的 $3 \times 3$ 区域：

5 5 5
1 5 1
5 5 5

最大值为 5，最小值为 1，差为 4。如果 $C \ge 4$，则该区域满足条件，区域内高度之和为 $5+5+5+1+5+1+5+5+5=37$。

以第 3 行第 3 列为左上角的 $3 \times 3$ 区域：

5 5 5
5 2 5
5 5 2

最大值为 5，最小值为 2，差为 3。如果 $C \ge 3$，则该区域满足条件，区域内高度之和为 $5+5+5+5+2+5+5+5+2=39$。

以第 3 行第 1 列为左上角的 $3 \times 3$ 区域：

5 5 5
5 2 5
5 5 5

最大值为 5，最小值为 2，差为 3。如果 $C \ge 3$，则该区域满足条件，区域内高度之和为 $5+5+5+5+2+5+5+5+5=40$。

因此当 $C \ge 3$ 时，答案为 40。

数据范围

对于所有测试点，保证 $1 \le K \le H, W \le 50$，$0 \le h_{i,j} \le 10^9$，$0 \le C \le 10^9$。

知识点与难度

本题涉及的知识点从属于 GESP四级（二维数组、枚举/模拟），难度等级：普及-。