Super Plumber

Πρέπει να γράψετε ένα πρόγραμμα για να παίξετε ένα βιντεοπαιχνίδι στο οποίο ο Super Plumber (SP) πλοηγείται σε μια διαδρομή με εμπόδια συλλέγοντας βραβεία στο δρόμο για τη διάσωση της Πριγκίπισσας (The Princess: TP).

Η διαδρομή εμποδίων είναι ένα ~m~ επί ~n~ πλέγμα. Ο SP ξεκινάει από την κάτω αριστερή γωνία και οδηγείται προς την TP στην κάτω δεξιά γωνία. Ορισμένες από τις θέσεις του πλέγματος καταλαμβάνονται από εμπόδια από τα οποία δεν μπορεί να περάσει το SP. Άλλα καταλαμβάνονται από χρυσά νομίσματα αξίας μεταξύ ~$1,00~ και ~$9,00~.

Το παιχνίδι είναι ένα παραδοσιακό παιχνίδι κύλισης, που σημαίνει ότι ο SP μπορεί να κινηθεί μόνο προς τα δεξιά, πάνω ή κάτω. Το SP μετακινείται κατά μία θέση στο πλέγμα τη φορά, πάντα σε μια γειτονική τοποθεσία χωρίς εμπόδια. Δεν μπορεί να καταλάβει οποιαδήποτε θέση που κατείχε προηγουμένως - αν μετακινηθεί προς τα πάνω, δεν μπορεί να μετακινηθεί προς τα κάτω μέχρι να κινηθεί δεξιά, αν κινηθεί προς τα κάτω δεν μπορεί να ανέβει μέχρι να κινηθεί δεξιά. Ο SP συλλέγει τα χρυσά νομίσματα σε τοποθεσίες που επισκέπτεται. Πρέπει να βρείτε τη μέγιστη δυνατή συνολική αξία των νομισμάτων που μπορεί να συλλέξει ο SP κατά τη διάσωση της TP.

Είσοδος

Η είσοδος έχει πολλές περιπτώσεις δοκιμής. Η πρώτη γραμμή κάθε δοκιμαστικής περίπτωσης περιέχει τα ~m~ και ~n~, και οι δύο είναι ακέραιοι αριθμοί, ~(2 \le m, n \le 100)~. Στη συνέχεια, το πλέγμα δίνεται ως ~m~ γραμμές με ~n~ χαρακτήρες η καθεμία. Ένα εμπόδιο συμβολίζεται με έναν αστερίσκο (*), ένα νόμισμα συμβολίζεται με ένα ψηφίο (από το ~1~ έως το ~9~) και μια κενή θέση συμβολίζεται με τελεία (.). Είναι πάντα δυνατό για τον SP να σώσει την TP. Μια γραμμή που περιέχει ~0~ ~0~ ακολουθεί την τελευταία περίπτωση δοκιμής.

Έξοδος

Εκτυπώστε μία γραμμή για κάθε δοκιμαστική περίπτωση δίνοντας το χρηματικό ποσό που μπορεί να συγκεντρώσει ο SP.

Παραδείγματα

input

5 10
..3.......
..........
..7.**....
.9**...1..
..8..9....
2 2
99
88
0 0

output

27
34

Επεξήγηση του παραδείγματος:

Το παράδειγμα εισόδου περιέχει δύο περιπτώσεις δοκιμής. Για την πρώτη περίπτωση, ο SP μπορεί να συγκεντρώσει ~27,00 $~ με την ακόλουθη σειρά κινήσεων: Up, Right, Down, Right, Right, Right, Right, Up, Right, Right, Down, Right, Right. Για τη δεύτερη περίπτωση, ο SP μπορεί να συγκεντρώσει ~34,00 $~ με την ακόλουθη σειρά: Up, Right, Down.