Apesar da prudência inata, as vacas perderam nas hipotecas e tentam ações. Bessie prevê preços: sabe os atuais de $S$ $(2 \le S \le 50)$ ações e futuros para um total de $D$ dias $(2 \le D \le 10)$.

Com matriz de preços atuais e futuros por dia $(1 \le PR_{sd} \le 1,000)$ e $M$ $(1 \le M \le 200,000)$ dinheiro inicial, encontre compras/vendas ótimas para maximizar ganho com venda final. Compram quantidades inteiras, não precisam gastar tudo nem nada. Lucro não excederá 500,000.

Exemplo de mercado em alta, favorito de Bessie: $S=2$, $D=3$, dinheiro 10 para investir. Colunas: preços hoje, amanhã, depois de amanhã.

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

Para ganhar compra ação 1 no dia 1. Vende no dia 2 e compra logo ação 2: 4 no banco e uma ação 2. Venda final traz 20, com banco total 24.

Entrada

• Linha 1: inteiros com espaços $S$, $D$, $M$.
• Linhas $2,\ldots,S+1$: linha $s+1$, $D$ preços $PR_{sd}$ da ação $s$ nos dias $1,\ldots,D$.

Saída

• Linha 1: máximo dinheiro após venda no dia $D$.

Exemplos

Entrada 1

2 3 10
10 15 15
13 11 20

Saída 1

24

Autor: Rob Kolstad(?), 2008