NEO

Time limit1sMemory limit256 MB

Summary

Find the largest submatrix with at least two rows and columns in which every submatrix meets the corner-sum inequality.

Level: Medium7 of 10
Topics: Matrix, Stack, Math
Solved: No attempts yet

Problem

Write $A_{i,j}$ for the element of matrix $A$ in row $i$ and column $j$ . A matrix $A$ with $r$ rows and $s$ columns is cool if both of these hold.

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

A matrix with at least two rows and at least two columns is extremely cool if every submatrix of it that has at least two rows and at least two columns is cool.

A submatrix is the rectangular region where a range of consecutive rows meets a range of consecutive columns.

Find an extremely cool submatrix of the given matrix and report the largest number of elements such a submatrix can have.

Input

The first line contains two integers $R$ and $S$ , the dimensions of the matrix ( $2 \le R, S \le 1000$ ).

Each of the next $R$ lines contains $S$ integers, one row of the matrix. Every element is an integer between $-10^6$ and $10^6$ .

Output

Print one line with the largest number of elements an extremely cool submatrix of the given matrix has. If the matrix has no extremely cool submatrix, print 0.

Examples3

Example 1
Input
```
3 3
1 4 10
5 2 6
11 1 3
```
Expected output
```
9
```
Example 2
Input
```
3 3
1 3 1
2 1 2
1 1 1
```
Expected output
```
4
```

Example 3

Input

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

Expected output