Mimo wrodzonej ostrożności krowy straciły na hipotekach i próbują akcji. Bessie przewiduje ceny: dzisiejsze $S$ $(2 \le S \le 50)$ akcji i przyszłe na łącznie $D$ dni $(2 \le D \le 10)$.

Dane ceny obecne i przyszłe w macierzy dni $(1 \le PR_{sd} \le 1,000)$ i początkowe $M$ $(1 \le M \le 200,000)$ pieniędzy. Znajdź optymalne kupno/sprzedaż dla maksymalnego zysku przy sprzedaży na koniec. Całkowite liczby akcji, nie trzeba wydawać wszystkiego ani niczego. Zysk nie przekroczy 500,000.

Przykład rosnącej hossy, ulubionej przez Bessie: $S=2$, $D=3$, inwestycja 10. Kolumny: ceny dziś, jutro, pojutrze.

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

Dla zysku kup akcję 1 dnia 1. Sprzedaj dnia 2 i szybko kup akcję 2: w banku 4 i jedna akcja 2. Ostatnia sprzedaż za 20 daje z bankiem 24.

Wejście

• Wiersz 1: całkowite $S$, $D$, $M$ ze spacjami.
• Wiersze $2,\ldots,S+1$: wiersz $s+1$, $D$ cen $PR_{sd}$ akcji $s$ w dniach $1,\ldots,D$.

Wyjście

• Wiersz 1: największe pieniądze po sprzedaży dnia $D$.

Przykład

Wejście 1

2 3 10
10 15 15
13 11 20

Wyjście 1

24

Autor: Rob Kolstad(?), 2008