#672. 平整地块

平整地块

题目描述

小 A 得到了一张 nnmm 列的山地高度图,第 ii 行第 jj 列的整数表示该位置的高度。现在要在图中选择一个 3×33\times3 的正方形地块。若这个 3×33\times3 地块内最高高度与最低高度之差不超过 HH,则认为该地块是平整地块。请统计平整地块的数量,并求所有平整地块中高度总和的最大值。如果不存在平整地块,输出 0 0

输入格式

第一行包含三个整数 nnmmHH,表示高度图的行数、列数和允许的最大高度差。

接下来 nn 行,每行包含 mm 个整数,表示高度图。

输出格式

输出一行,包含两个整数,分别表示平整地块的数量和所有平整地块中高度总和的最大值。如果不存在平整地块,输出 0 0

样例

3 3 2
1 2 3
2 2 3
3 3 3
1 22
4 4 0
1 1 1 2
1 1 1 2
1 1 1 2
3 3 3 3
1 9

样例解释

样例 11 中,只有一个 3×33\times3 地块,其最高高度为 33、最低高度为 11,差为 22,不超过 HH,高度总和为 2222

样例 22 中,左上角的 3×33\times3 地块全部由 11 组成,是唯一的平整地块,高度总和为 99

数据范围

对于所有测试数据,1n,m5001 \le n,m \le 5000H1090 \le H \le 10^900 \le 每个高度 109\le 10^9

n<3n<3m<3m<3,则不存在 3×33\times3 地块。

建议使用 long long 保存高度总和。