Coste mínimo en un tablero P75734

Considerad un tablero n × m, donde cada casilla contiene el coste de pasar por ella. Tenéis que comenzar en la fila de arriba (0) y acabar en la fila de abajo (n−1) con el mínimo coste posible, haciendo siempre movimientos que incrementen la fila donde os encontráis. En general, sólo podéis moveros a casillas adyacentes (verticalmente o en diagonal), con una excepción: podéis hacer un máximo de k saltos de un caballo de ajedrez (siempre hacia abajo, hasta cuatro opciones posibles).

Entrada

La entrada consiste en varios casos, sólo con números naturales. Cada caso empieza con n, m y k, seguidas de n filas con m costes. Suponed que n y m están entre 1 y 100, que k está entre 0 y 100, y que los costes están entre 0 y 10⁴.

Salida

Para cada caso, escribid el mínimo coste de ir desde la fila de arriba hasta la fila de abajo haciendo como máximo k saltos de caballo. Podéis comenzar y acabar en las columnas que queráis.