Pese a su prudencia innata, las vacas perdieron en hipotecas y prueban acciones. Bessie ve el futuro: sabe los precios de hoy de $S$ $(2 \le S \le 50)$ acciones y futuros para $D$ días $(2 \le D \le 10)$ en total.

Dados precios actuales y futuros por día $(1 \le PR_{sd} \le 1,000)$ e inicial $M$ $(1 \le M \le 200,000)$ dinero, busca compras/ventas óptimas para máxima ganancia al vender el día final. Se compran cantidades enteras de acciones, sin obligación de gastar todo ni algo. Beneficio no superior a 500,000 garantizado.

Ejemplo de mercado alcista, favorito de Bessie: $S=2$, $D=3$, inversión 10. Columnas: precios hoy, mañana, pasado mañana.

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

Para ganar compra acción 1 el día 1. Vende el día 2 y compra rápidamente acción 2: 4 en banco y una acción 2. Venta final da 20, con banco total 24.

Entrada

• Línea 1: enteros con espacios $S$, $D$, $M$.
• Líneas $2,\ldots,S+1$: línea $s+1$, $D$ precios $PR_{sd}$ de acción $s$ en días $1,\ldots,D$.

Salida

• Línea 1: máximo dinero tras vender en día $D$.

Ejemplos

Entrada 1

2 3 10
10 15 15
13 11 20

Salida 1

24

Autor: Rob Kolstad(?), 2008