Let us denote as the element from matrix
located in the
row and
column. We say that the matrix
is cool if this holds:
where denotes the number of rows, and
the number of columns of matrix
.
Additionally, we say that a matrix is extremely cool if each of its submatrices with at least two rows and two columns is cool.
It is your task to determine the largest number of elements that are contained in an extremely cool submatrix of the given matrix.
Input
The first line of input contains two integers
which represent the dimensions of the matrix.
Each of the following lines contains
integers that represent the elements in the matrix. The elements in the matrix will be integers from the interval
.
Output
The first and only line of output must contain the maximal number of elements that are contained in an extremely cool submatrix of the matrix from the input. If an extremely cool submatrix doesn't exist, output 0
.
Scoring
In test cases worth 60% of total points, it will additionally hold .
Sample Input 1
3 3
1 4 10
5 2 6
11 1 3
Sample Output 1
9
Sample Input 2
3 3
1 3 1
2 1 2
1 1 1
Sample Output 2
4
Sample Input 3
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
Sample Output 3
15
Explanation for Sample Output 3
The solution is a matrix with an upper left corner in and lower right corner in
.
Comments