G - One More Grid Task Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 575 点

問題文

N \times M のグリッドがあり、上から i 行目、左から j 列目のマス (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 を選ぶ。
  • このとき、整数 i,j が l_x \le i \le r_x かつ l_y \le j \le r_y を満たす、またその時に限って、マス (i,j) は R に含まれる。

適切に R を選ぶことによって、 f(R) = ( R 内のマスに書かれた整数の総和 ) \times ( R 内のマスに書かれた整数の最小値 ) として達成可能な最大値を求めてください。

制約

  • 入力は全て整数
  • 1 \le N,M \le 300
  • 1 \le A_{i,j} \le 300

入力

入力は以下の形式で標準入力から与えられる。

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}

出力

答えを整数として出力せよ。

入力例 1

3 3
5 4 3
4 3 2
3 2 1

出力例 1

48

左上がマス (1,1) 、右下がマス (2,2) の長方領域を選ぶことで、 f(R) = (5+4+4+3) \times \min(5,4,4,3) = 48 が達成でき、これが達成可能な最大値です。

入力例 2

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

出力例 2

231

入力例 3

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

出力例 3

810000

Score : 575 points

Problem Statement

There is an N \times M grid, where the square at the i-th row from the top and j-th column from the left has a non-negative integer A_{i,j} written on it.
Let us choose a rectangular region R.
Formally, the region is chosen as follows.

  • Choose integers l_x, r_x, l_y, r_y such that 1 \le l_x \le r_x \le N, 1 \le l_y \le r_y \le M.
  • Then, square (i,j) is in R if and only if l_x \le i \le r_x and l_y \le j \le r_y.

Find the maximum possible value of f(R) = (the sum of integers written on the squares in R) \times (the smallest integer written on a square in R).

Constraints

  • All input values are integers.
  • 1 \le N,M \le 300
  • 1 \le A_{i,j} \le 300

Input

The input is given from Standard Input in the following format:

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}

Output

Print the answer as an integer.

Sample Input 1

3 3
5 4 3
4 3 2
3 2 1

Sample Output 1

48

Choosing the rectangular region whose top-left corner is square (1, 1) and whose bottom-right corner is square (2, 2) achieves f(R) = (5+4+4+3) \times \min(5,4,4,3) = 48, which is the maximum possible value.

Sample Input 2

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

Sample Output 2

231

Sample Input 3

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

Sample Output 3

810000