题目描述

在地形图中选择一个连续的 $3\times3$ 区域作停机坪。九个格子的最高与最低海拔之差不能超过 $H$。求所有合格区域中，九格海拔总和的最大值。

输入格式

第一行给出行数 $M$、列数 $N$ 及高度差上限 $H$。随后 $M$ 行各给出 $N$ 个整数 $a_{ij}$，表示各格的海拔。

输出格式

输出符合条件的最大海拔总和。

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\le10^3$，$1\le H,a_{ij}\le10^5$。保证至少存在一个合格区域。

来源

洛谷 B4451 · CCF GESP C++ 四级。