Coste mínimo en un tablero P75734

Considerad un tablero $n \times 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^4$.

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.