Problem
En una tabla rectangular NxM (en cada celda en la que está escrito un número determinado), al principio el jugador se encuentra en la celda superior izquierda.
En un movimiento, se le permite moverse a la siguiente celda, ya sea hacia la derecha o hacia abajo (está prohibido moverse hacia la izquierda y hacia arriba).
Al atravesar una celda, el jugador paga tanto c.u.
Se requiere encontrar la cantidad mínima de u.c., pagando la cual el jugador puede llegar a la esquina inferior derecha.
Entrada:
- la primera línea contiene dos números N y M - tamaños de tabla (\(1<=N<=20 \), \(1<=M<=20\));
- luego hay N líneas de M números en cada una - tamaños de multas en c.u. para pasar por las celdas correspondientes (cada número del 0 al 100).
Salida: imprime la cantidad mínima que puedes gastar para obtener en la esquina inferior derecha.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
8 |