XXVI Olimpíada Brasileira de Informática
Nova avenida
O bairro Boa Vista é formado por um conjunto de quadras de mesmo tamanho, dispostas em um quadriculado de N por M quadras, com ruas no sentido Norte-Sul e no sentido Leste-Oeste. Assim, o comprimento de cada rua no sentido Norte-Sul é igual a N quadras e o comprimento de cada rua no sentido Leste-Oeste é igual a M quadras. A atual administração da prefeitura decidiu que é necessário escolher uma rua do bairro, no sentido Norte-Sul, para ser alargada. Para isso, será necessário desapropriar todas as quadras de um dos lados da rua escolhida. As quadras têm construções diferentes, de forma que cada quadra tem um valor diferente no mercado. Para desapropriar as quadras, a prefeitura tem que pagar o valor do mercado aos proprietários. A figura abaixo mostra um exemplo dos valores das quadras, em milhões de reais, onde N=3 e M=4.
Entrada
A primeira linha da entrada contém dois inteiro N e M que indicam respectivamente o número de quadras no sentido Norte-Sul e no sentido Leste-Oeste. Cada uma das N linhas seguintes corresponde a uma das N fileiras de quadras no sentido Leste-Oeste e contém M inteiros, que são os valores das quadras daquela fileira de quadras, visualizada no sentido Leste-Oeste.Saída
Seu programa deve imprimir uma única linha, contendo um único inteiro, que é o menor valor, em milhões de reais, que a prefeitura vai precisar desembolsar.Restrições
A entrada obedece às seguintes restrições:- 2 ≤ N ≤ 1000
- 2 ≤ M ≤ 1000
- cada quadra tem valor entre 1 e 100 milhões de reais
Exemplos
Entrada
3 4 5 3 12 4 5 4 7 2 5 1 10 5 |
Saída
8 |
Entrada
4 5 20 30 10 10 50 20 30 10 10 50 20 30 10 10 50 20 30 10 10 50 |
Saída
40 |
