Camí de benefici màxim P32049

Considereu un tauler f × c, on cada casella té un valor positiu. Us trobeu a la casella de dalt a l’esquerra, i heu d’anar a la de baix a la dreta, sense sortir mai del tauler. Cada pas l’heu de fer cap a baix o cap a la dreta, amb una excepció: podeu fer s salts del cavall dels escacs (cadascun, de qualsevol de les vuit maneres possibles). Cada vegada que passeu per una casella n’acumuleu el valor. Optimitzeu el benefici.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb f, c i s, seguit de f files amb c nombres naturals entre 1 i 10⁵. Suposeu que f i c estan ambdues entre 3 i 100, i que s està entre 0 i 100.

Sortida

Per a cada cas, escriviu el màxim benefici possible.