1638. [IOI 1999]矩形地块（A Strip of Land）

【题目描述】

$Dingilville$的居民正设法找到一块地来修建机场。他们已经有了这片地区的地图。地图是一个由单位格组成的矩形网格，每个单位格由一个整数对$(x,y)$确定，其中 $x$ 是横坐标（东到西），$y$ 是纵坐标（南到北）,地图中标注了每格的海拔。

你的任务是找到一个由单位格组成的，面积最大（即包含最多单位格）的矩形地块，使得：

·地块中海拔 最高 和 最低 的单位格的 海拔之差 不超过给定的限制 $C$；

·地块的宽度（即从西到东的距离）不超过 $100$；

你需要输出满足条件地块的最大面积。

【输入格式】

输入文件的第一行有三个整数 $M,N,C$，代表地图的大小和给定限制。

接下来的 $N$ 行，每行有 $M$ 个整数 $H_{xy}$，给出了每格的海拔。

【输出格式】

输出一行一个正整数，即最大面积。

【样例输入】

10 15 4
41 40 41 38 39 39 40 42 40 40
39 40 43 40 36 37 35 39 42 42
44 41 39 40 38 40 41 38 35 37
38 38 33 39 36 37 32 36 38 40
39 40 39 39 39 40 40 41 43 41
39 40 41 38 39 38 39 39 39 42
36 39 39 39 39 40 39 41 40 41
31 37 36 41 41 40 39 41 40 40
40 40 40 42 41 40 39 39 39 39
42 40 44 40 38 40 39 39 37 41
41 41 40 39 39 40 41 40 39 40
47 45 49 43 43 41 41 40 39 42
42 41 41 39 40 39 42 40 42 42
41 44 49 43 46 41 42 41 42 42
45 40 42 42 46 42 44 40 42 41

【样例输出】

35

【提示】

样例如图：

【数据规模与约定】

对于 $10\%$ 的数据，$1<=N,M<=20, C=0, 0<=H_{xy}<=20000$;

对于 $100\%$ 的数据，$1<=N,M<=700, 0<=C<=10, -30000<=H_{xy}<=30000$;

西南角是$（1,1）$，东北角是$（M,N）$;

【来源】

IOI 1999 Day2 Pro3 A Strip of Land