Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 3 de Abril
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #02]

[DAA 008] Um jogo com matrizes

O Pedro e a Luísa decidiram estender o seu jogo para duas dimensões! Um deles escreve uma matriz de números inteiros (positivos ou negativos) e o outro tem de tentar descobrir qual a submatriz (um subretângulo contido na matriz) que dá origem à maior soma possível.

Imagina por exemplo que a Luísa escolhe a seguinte matriz:

Alguns exemplos de submatrizes seriam as seguintes (indicadas a vermelho):

A última destas submatrizes corresponde precisamente à melhor subretângulo possível que o Pedro poderia escolher, ou seja, o que tem maior soma.

Podes ajudar os dois amigos a jogarem este jogo?

O Problema

Dada uma matriz de L linhas por C colunas contendo números inteiros, a tua tarefa é calcular a maior soma que uma sua submatriz não vazia pode ter.

Input

Na primeira linha do input vêm dois inteiros L e C, indicando respetivamente a quantidade de linhas e colunas da matriz.

Seguem-se L linhas, cada uma exactamente C números inteiros m_ij, indicando a matriz a considerar.

Output

O output é constituído por uma única linha contendo a soma máxima de uma submatriz, como atrás descrito.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Exemplo de Input

4 4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1 
-1 8 0 -2

Exemplo de Output

15

Explicação do Input/Output

O exemplo de input corresponde ao exemplo explicado no enunciado do problema.

Desenho e Análise de Algoritmos (CC2001)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto