Submatriz com a soma máxima

Dada uma matriz de inteiros de dimensão , pretende-se calcular a submatriz que apresente a maior soma.

Entrada

A primeira linha da entrada contém dois inteiros — o número de linhas da matriz r e o número de colunas c (1 ≤ r, c ≤ 50).

As próximas r linhas contêm c inteiros separados por espaço, que representam os elementos da matriz .

Saída

O programa deve imprimir um único inteiro: a maior soma de uma submatriz.

Exemplos

Entrada

Saída

3 5
1 2 -3 4 -6
-1 3 -100 4 0
0 1 -2 0 100

104

Explicação

1

2

-3

4

-6

-1

3

-100

4

0

0

1

-2

0

100

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue