SPOJ Brasil

Pequeno Charlie é um bom garoto viciado em doces. Ele até assina a Revista Todos Doces (All Candies Magazine) e foi selecionado para participar na Competição Internacional de Coleta de Doces (International Candy Picking Contest).

Nessa competição um número aleatório de caixas contendo doces são dispostas em M linhas com N colunas cada (então, existe um total de M x N caixas). Cada caixa tem um número indicando quantos doces ela contém.

O competidor pode pegar uma caixa (qualquer uma) e pegar todos os doces dentro dela. Mas existe uma sacada (sempre existe uma sacada): quando uma caixa é escolhida, todas as caixas das linhas logo acima e logo abaixo são esvaziadas, assim como as caixas à direita e à esquerda da caixa escolhida. O competidor continua pegando uma caixa até que não hajam mais doces.

A figura abaixo ilustra isso, passo a passo. Cada célula representa uma caixa e o número de doces que ela contém. A cada passo, a caixa escolhida é circulada e as células sombreadas representam as caixas que serão esvaziadas. Após oito etapas o jogo acaba e Charlie pegou 10 + 9 + 8 + 7 + 6 + 10 + 1 = 54 doces.

Para pequenos valores de M e N, Charlie consegue achar o número máximo de doces que ele consegue coletar facilmente, mas quando os números são muito grandes ele começa a se perder. Você pode ajudar Charlie a maximizar o número de doces que ele pode pegar?

Entrada

A entrade contém vários casos de teste. A primeira linha de um caso de teste contém dois números inteiros M e N (1 <= M x N <= 10^5), separados por um espaço, indicando o número de linhas e colunas, respectivamente. Cada uma das M linhas seguintes contém N inteiros separados por espaço, cada uma representando o número inicial de doces na caixa correspondente. Cada caixa terá inicialmente pelo menos 1 e no máximo 10^3 doces.

O final da entrade é indicado por uma linha contendo dois zeros separados por um espaço.

Saída

Para cada caso de teste da entrada, seu programa deve imprimir uma única linha, contendo um único valor, o inteiro indicando o número máximo de doces que Charlie pode pegar.

Exemplo de entrada
5 5
1 8 2 1 9
1 7 3 5 2
1 2 10 3 10
8 4 7 9 1
7 1 3 1 6
4 4
10 1 1 10
1 1 1 1
1 1 1 1
10 1 1 10
2 4
9 10 2 7
5 1 1 5
0 0

Saída para o exemplo de entrada
54
40
17