시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB34191651.613%

문제

Let us denote Ai,j as the element from matrix A located in the ith row and jth column. We say that the matrix A is cool if this holds:

  • r, s > 1
  • A1,1 + Ar,s ≤ A1,s + Ar,1

where r denotes the number of rows, and s the number of columns of matrix A.

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.

입력

The first line of input contains two integers R, S (2 ≤ R, S ≤ 1 000) which represent the dimensions of the matrix.

Each of the following R lines contains S integers that represent the elements in the matrix. The elements in the matrix will be integers from the interval [−106, 106].

출력

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.

예제 입력 1

3 3
1 4 10
5 2 6
11 1 3

예제 출력 1

9

예제 입력 2

3 3
1 3 1
2 1 2
1 1 1

예제 출력 2

4

예제 입력 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

예제 출력 3

15

힌트

Clarification of the third example: The solution is a matrix with an upper left corner in (3,2) and lower right corner in (5,6).