Problem
In der rechteckigen Tabelle NxM (in jeder Zelle ist eine Zahl geschrieben) befindet sich der Spieler am Anfang in der oberen linken Zelle.
In einem Zug darf er sich entweder nach rechts oder nach unten in eine benachbarte Zelle bewegen (links und oben ist verboten).
Beim Passieren einer Zelle nimmt der Spieler so viel Geld vom Spieler ab, wie die Zahl in dieser Zelle geschrieben ist (das Geld wird auch für die erste und letzte Zelle seines Weges genommen).
Es ist erforderlich, den Mindestbetrag zu finden, den der Spieler mit der Zahlung in die untere rechte Ecke gelangen kann.
Eingabe:
- in der ersten Zeile sind zwei Zahlen angegeben: N und M - Tabellengrößen (\(1<=N<=20\), \(1<=M<=20\));
- als nächstes kommen die N Zeilen nach den M Zahlen in jedem - die Größe der Strafen in cu für den Durchgang durch die entsprechenden Zellen (jede Zahl von 0 bis 100).
Ausgabe: Geben Sie den Mindestbetrag aus, den Sie ausgeben können, um in die untere rechte Ecke zu gelangen.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
3 4
1 1 1 1
5 2 2 100
9 4 2 1
|
8 |