رغم الحذر الفطري خسرت الأبقار في الرهن العقاري فتجرب الأسهم. 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$ للسهم $s$ في أيام $1,\ldots,D$: $PR_{sd}$.

الإخراج

• السطر 1: أكبر مال بعد البيع يوم $D$.

أمثلة

الإدخال 1

2 3 10
10 15 15
13 11 20

الإخراج 1

24

المؤلف: Rob Kolstad(?)، 2008