למרות זהירותן הטבעית הפרות הפסידו במשכנתאות ומנסות מניות. Bessie חוזה עתיד: מחירי היום של $S$ $(2 \le S \le 50)$ מניות וגם העתיד לסך $D$ ימים $(2 \le D \le 10)$.

עם מטריצת מחירים נוכחיים ועתידיים לימים $(1 \le PR_{sd} \le 1,000)$ וכסף ראשוני $M$ $(1 \le M \le 200,000)$, מצאו קנייה ומכירה אופטימליות לרווח מרבי במכירה ביום האחרון. קונים כמויות שלמות, לא חייבים להוציא הכול או משהו בכלל. מובטח רווח לא מעל 500,000.

דוגמת שוק עולה המועדף על Bessie: $S=2$, $D=3$, להשקעה 10. עמודות: מחיר היום, מחר, מחרתיים.

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

כדי להרוויח קונים מניה 1 ביום 1. מוכרים ביום 2 וקונים מהר מניה 2: בבנק 4 ומניה אחת של 2. מכירה ביום האחרון מביאה 20 וביחד עם הבנק 24.

קלט

• שורה 1: שלמים $S$, $D$, $M$ ברווחים.
• שורות $2,\ldots,S+1$: שורה $s+1$ מכילה $D$ מחירים $PR_{sd}$ למניה $s$ בימים $1,\ldots,D$.

פלט

• שורה 1: כסף מרבי אחרי מכירה ביום $D$.

דוגמאות

קלט 1

2 3 10
10 15 15
13 11 20

פלט 1

24

מחבר: Rob Kolstad(?), 2008