Matriz super-legal

Denotando por $A_{i,j}$ o elemento na $i$-ésima linha e $j$-ésima coluna da matriz $A$, dizemos que uma matriz é “legal” se a condição $$A_{1,1} + A_{lin,col} \leq A_{1,col} + A_{lin,1}$$ é verdadeira para todo $lin > 1$ e $col > 1$.

Adicionalmente, dizemos que a matriz é “super-legal” se cada uma de suas submatrizes com pelo menos duas linhas e duas colunas é legal. Lembre que uma submatriz $S$ de uma matriz $M_{L\times C}$ é uma matriz que inclui todos os elementos $M_{i,j}$ tais que $l_1 \leq i \leq l_2$ e $c_1 \leq j \leq c_2$, para $1 \leq l_1 \leq l_2 \leq L$ e $1 \leq c_1 \leq c_2 \leq C$.

A sua tarefa é, dada uma matriz $A$, determinar a maior quantidade de elementos de uma submatriz super-legal da matriz $A$.

Entrada

A primeira linha contém dois inteiros $L$ e $C$ indicando respectivamente o número de linhas e o número de colunas da matriz. Cada uma das $L$ linhas seguintes contém $C$ inteiros $X_i$ representando os elementos da matriz.

Saída

Seu programa deve produzir uma única linha, contendo uma única linha, com apenas um número inteiro, a maior quantidade de elementos de uma submatriz super-legal da matriz da entrada, ou zero no caso de não existir uma submatriz super-legal.

Restrições

• $2 \leq L,C \leq 1\ 000$
• $-10^6 \leq X_i \leq 10^6$

Informações sobre a pontuação

• Para um conjunto de casos de testes valendo $10$ pontos, $L,C \leq 3$.
• Para um conjunto de casos de testes valendo outros $50$ pontos, $L,C \leq 300$.

Exemplos

Exemplo de entrada 1

3 3
1 4 10
5 2 6
11 1 3

Exemplo de saída 1

9

Exemplo de entrada 2

3 3
1 3 1
2 1 2
1 1 1

Exemplo de saída 2

4

Exemplo de entrada 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

Exemplo de saída 3

15