Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DOCE - Doces

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


Adicionado por:Wanderley Guimarăes
Data:2009-01-18
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Final Sul-Americana da Maratona de Programação da ACM 2008

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.