El tresor de Barbanegra P56935

La llegenda diu que, en l’última expedició del famós pirata Barbanegra, el vaixell va ser tombat en una tràgica tempesta, i tots els sacs d’or que hi portava van caure al fons del mar, en un lloc que mai més va ser transitat durant centenars d’anys. Això fins que un bon dia, navegant en la teva petita barca de pescador, pesques un dels sacs d’or. Mirant al fons del mar, veus la resta del tresor. Hora de fer-se ric!

El mar es modelitza amb una graella d’n files i m columnes. Si una casella està buida, ho representem amb un punt, i si conté un sac amb 1 ≤ k ≤ 9 monedes d’or, ho representem amb el nombre k. El teu vaixell pot començar a qualsevol casella de la fila de dalt, i a cada pas es pot moure una casella cap a baix, diagonalment a baix a l’esquerra o diagonalment a baix a la dreta, fins arribar a la fila de baix. En cap moment pots sortir de la graella. Si el vaixell passa per sobre d’una casella amb un sac d’or (incloent la inicial i la final), aleshores pesques aquell sac. Quin és el nombre màxim de monedes d’or que pots obtenir?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, seguits d’una graella n × m, on cada casella conté un punt o un natural entre 1 i 9.

Sortida

Per a cada cas, escriu el nombre màxim de monedes que pots obtenir.