3455 - [GESP四级202512] 建造(build)

题目描述

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

停机坪为一个 3 \times 3 的区域且内部所有 9 个点的最大高度和最小高度之差不超过 H

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

输入

第一行三个正整数 M, N, H,含义如题面所示。

之后 M 行,第 i 行包含 N 个整数 a_{i1}, a_{i2}, \ldots, a_{iN},代表坐标 (i, j) 的高度。

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

输出

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

样例

输入

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

输出

40
说明

说明/提示

数据范围

对于所有测试点,保证 1 \le M, N \le 10^31 \le H, a_{ij} \le 10^5

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 97
通过人数 49
金币数量 3 枚
难度 基础


上一题 下一题