Problem Description

A matrix $A$ is a "YF matrix" if and only if it satisfies:

• $r,s>1$.
• $A_{1,1}+A_{r,s}\le A_{1,s}+A_{r,1}$.

Here, $r$ and $s$ are the numbers of rows and columns of matrix $A$, respectively.

Also, if every submatrix of a matrix with size at least $2\times2$ is a "YF matrix", then we call this matrix a "Sept matrix".

Given a matrix $A$, you need to find the number of elements in the largest submatrix of $A$ that is a "Sept matrix".

Input Format

The first line contains two integers $R,S$, which are the numbers of rows and columns of $A$, respectively.

The next $R$ lines each contain $S$ integers, describing matrix $A$.

Output Format

Output one line: the number of elements in the largest submatrix of $A$ that is a "Sept matrix".

If no such submatrix exists, output $0$.

3 3
1 4 10
5 2 6
11 1 3

9

3 3
1 3 1
2 1 2
1 1 1

4

5 6
1 1 4 0 3 3
4 4 9 7 11 13
-3 -1 4 2 8 11
1 5 9 5 9 10
4 8 10 5 8 8

15

Hint

Explanation for Sample 3

The top-left and bottom-right coordinates of the largest submatrix that is a "Sept matrix" are $(3,2)$ and $(5,6)$, respectively.

Constraints

• For $60\%$ of the testdata, $R,S\le 350$.
• For $100\%$ of the testdata, $2\le R,S\le 10^3$, and $A_{i,j}\in[-10^6,10^6]$.

Notes

According to the original problem settings, the full score is 140 points.

Translated from COCI 2014-2015 Contest #6 Task E NEO.

Translated by ChatGPT 5