Problem
Em uma mesa retangular NxM (em cada célula da qual um determinado número é escrito), no início o jogador está na célula superior esquerda.
Em um movimento, ele pode mover para a próxima célula tanto para a direita quanto para baixo (é proibido mover para a esquerda e para cima).
Ao passar por uma célula, o jogador é cobrado tanto c.u.
É necessário encontrar o valor mínimo de u.c., pagando o qual o jogador pode chegar ao canto inferior direito.
Entrada:
- a primeira linha contém dois números N e M - tamanhos de tabela (\(1<=N<=20 \), \(1<=M<=20\));
- então há N linhas de M números em cada - tamanhos de multas em c.u. para passar pelas células correspondentes (cada número de 0 a 100).
Saída: imprima o valor mínimo que você pode gastar para obter no canto inferior direito.
Exemplos
| # |
Entrada |
Saída |
| 1 |
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
8 |