Trotz angeborener Vorsicht verloren die Kühe am Hypothekenmarkt und versuchen Aktien. Bessie sieht voraus: Sie kennt heutige Preise von $S$ $(2 \le S \le 50)$ Aktien und zukünftige für insgesamt $D$ Tage $(2 \le D \le 10)$.

Gegeben Preismatrix heute/zukünftig je Tag $(1 \le PR_{sd} \le 1,000)$ und Startgeld $M$ $(1 \le M \le 200,000)$. Finde optimale Käufe/Verkäufe für maximalen Gewinn beim Verkauf am letzten Tag. Nur ganze Aktienzahlen, weder alles noch überhaupt Geld muss ausgegeben werden. Gewinn höchstens 500,000 garantiert.

Beispiel eines steigenden Bullenmarkts, Bessies Lieblingsmarkt: $S=2$, $D=3$, Investitionsgeld 10. Spalten: Preise heute, morgen, übermorgen.

                   Today's price
                   |   Tomorrow's price
                   |   |  Two days hence
             Stock |   |  | 
              1    10 15 15
              2    13 11 20

Für Gewinn Aktie 1 am Tag 1 kaufen. Tag 2 verkaufen und sofort Aktie 2 kaufen: 4 auf der Bank, eine Aktie 2. Endverkauf bringt 20, plus Bank insgesamt 24.

Eingabe

• Zeile 1: ganze Zahlen mit Leerzeichen $S$, $D$, $M$.
• Zeilen $2,\ldots,S+1$: Zeile $s+1$, $D$ Preise $PR_{sd}$ der Aktie $s$ an Tagen $1,\ldots,D$.

Ausgabe

• Zeile 1: größtes Geldvermögen nach Verkauf am Tag $D$.

Beispiele

Eingabe 1

2 3 10
10 15 15
13 11 20

Ausgabe 1

24

Autor: Rob Kolstad(?), 2008