Cost mínim en un tauler P75734

Considereu un tauler $n \times m$, on cada casella conté el cost de passar-hi. Heu de començar a la fila de dalt (0) i acabar a la fila de baix ($n-1$) amb el mínim cost possible, fent sempre moviments que incrementin la fila on us trobeu. En general, només us podeu moure a caselles adjacents (verticalment o en diagonal), amb una excepció: teniu dret a fer un màxim de $k$ salts de cavall dels escacs (sempre cap avall, fins a quatre opcions possibles).

Entrada

L’entrada consisteix en diversos casos, només amb nombres naturals. Cada cas comença amb $n$, $m$ i $k$, seguides d’$n$ files amb $m$ costs. Suposeu que $n$ i $m$ estan entre 1 i 100, que $k$ està entre 0 i 100, i que els costs estan entre 0 i $10^4$.

Sortida

Per a cada cas, escriviu el mínim cost d’anar des de la fila de dalt fins a la fila de baix fent com a màxim $k$ salts de cavall. Podeu començar i acabar a les columnes que vulgueu.