Ski P84876

De repente, el ski se ha puesto de moda en Barcelona. Aprovechando las nevadas recientes, la gente se dedica a buscar una calle (nevada) con suficiente pendiente y se lanza esquiando desde arriba del todo, con el objetivo de llegar a la parte de abajo de la calle tan rápidamente como sea posible. ¡Ayúdales a encontrar el mejor camino!

La calle es una cuadrícula de $N$ filas de $M$ columnas. Por cada casilla se da el tiempo (en décimas) que se tarda en atravesarla. El esquiador empieza en cualquier casilla de la primera fila, y únicamente puede desplazarse hacia abajo, en línea recta (la casilla inmediatamente inferior a la que ocupa) o en diagonal (la que queda a la izquierda o a la derecha de la anterior casilla). Cada desplazamiento en diagonal penaliza con una décima adicional. El esquiador no puede salir de la cuadrícula.

Entrada

Una secuencia de casos de prueba. Cada caso de pruebas está formado por dos números $N, M>0$ separados por un espacio, y $N$ líneas de $M$ dígitos (0-9) cada una con los tiempos (en décimas) que tarda el esquiador en cruzar la casilla. Dos casos de prueba se separarán por una línea en blanco.

Salida

Una única línea por cada caso de pruebas, con el mínimo número de décimas necesario para realizar todo el descenso.

Puntuación

• TestA:   Una entrada con 100 casos de prueba con $N,M<10$.

• TestB:   Una entrada con 10 casos de prueba con $N,M<500$.