海盗迪克终于厌倦了在公海上的战斗、掠夺、偷窃以及让许多人生活在痛苦之中。于是他决定退休,并找到了一个完美的岛屿来度过余生,前提是他不会花光所有的钱。他现在有很多金币,他想把它们存放在一个箱子里(毕竟他是个海盗)。迪克可以建造一个矩形箱子,其顶部的尺寸不超过指定的上限,高度为任意整数。现在他需要一个地方来隐藏这个箱子。在探索岛屿时,他找到了一个完美的解决方案。
迪克将通过把箱子沉入一个浑浊的池塘来隐藏它。池塘有一个矩形的表面,它完全填满了一个有着高耸垂直岩壁的山谷底部。迪克勘测了池塘,并知道了放置在池塘表面的笛卡尔坐标网格系统中每个方格的深度。当迪克沉下箱子时,它会尽可能地沉下去,直到触及底部。箱子的顶部将保持与池塘表面平行,并且箱子将与网格方格对齐。被沉入的箱子排出的水会抬高池塘表面的水位(即使箱子周围没有空间让排出的水上升,这种情况也会发生)。山谷的岩壁足够高,水永远不会溅出山谷。当然,由于箱子必须是不可见的,它的顶部必须严格低于池塘的表面。你的任务是找到海盗迪克能以这种方式隐藏的箱子的最大体积。
在图 I.1 中,最左侧的图像显示了一个池塘,中间的图像显示了一个体积为 3 的箱子的可能放置方式,最右侧的图像显示了一个体积为 4 的箱子的放置方式,这是可能的最大体积。注意,如果第二个箱子再高一个单位,它的顶部就会可见,因为它将正好与水面齐平。
图 I.1:样例输入 1 的说明。
输入格式
输入包含一组测试用例。测试用例的第一行包含四个整数 $a, b, m$ 和 $n$ ($1 \le a, b, m, n \le 500$)。池塘表面的尺寸为 $m \times n$,箱子顶部(和底部)的最大尺寸为 $a \times b$。此外,$a$ 和 $b$ 足够小,以至于不可能用一个顶部尺寸为 $a \times b$ 的箱子覆盖整个池塘。接下来的 $m$ 行中,每一行包含 $n$ 个整数 $d_{i,j}$,表示池塘在网格方格 $(i, j)$ 处的深度,其中对于每个 $1 \le i \le m$ 和 $1 \le j \le n$,都有 $0 \le d_{i,j} \le 10^9$。
输出格式
输出一个矩形箱子的最大体积,该箱子的尺寸为整数(顶部的一维尺寸不超过 $a$,另一维尺寸不超过 $b$),且可以完全沉没在池塘表面之下。如果池塘中无法隐藏任何箱子,则输出 0。
样例
样例输入 1
3 1 2 3 2 1 1 2 2 1
样例输出 1
4
样例输入 2
4 1 1 5 2 0 2 2 2
样例输出 2
12
样例输入 3
2 3 3 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
样例输出 3
18