再一个网格问题

题目描述

有一个 $N \times M$ 的网格,第 $i$ 行(从上往下数)、第 $j$ 列(从左往右数)的格子上写有非负整数 $A_{i,j}$。

我们选择一个矩形区域 $R$。

形式化地说,区域按如下方式选择:

选择满足 $1 \le l_x \le r_x \le N$、$1 \le l_y \le r_y \le M$ 的整数 $l_x, r_x, l_y, r_y$。

那么,当且仅当 $l_x \le i \le r_x$ 且 $l_y \le j \le r_y$ 时,格子 $(i,j)$ 属于 $R$。

求 $f(R) =$($R$ 中所有格子上的整数之和)$\times$($R$ 中所有格子上的整数的最小值)的最大可能值。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,M}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,M}$
$\vdots$
$A_{N,1}$ $A_{N,2}$ $\dots$ $A_{N,M}$

输出格式

以整数形式输出答案。

样例

3 3
5 4 3
4 3 2
3 2 1

48

选择左上角为 $(1, 1)$、右下角为 $(2, 2)$ 的矩形区域时,$f(R) = (5+4+4+3) \times \min(5,4,4,3) = 48$,这是可能的最大值。

4 5
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4

231

6 6
1 300 300 300 300 300
300 1 300 300 300 300
300 300 1 300 300 300
300 300 300 1 300 300
300 300 300 300 1 300
300 300 300 300 300 1

810000

数据范围

• 输入中的所有值均为整数。
• $1 \le N,M \le 300$
• $1 \le A_{i,j} \le 300$