Dù vốn thận trọng, bò thua ở thị trường thế chấp nhà và thử cổ phiếu. Bessie tiên tri biết giá hôm nay của $S$ $(2 \le S \le 50)$ cổ phiếu và tương lai trong tổng $D$ ngày $(2 \le D \le 10)$.

Cho ma trận giá hiện tại/tương lai các ngày $(1 \le PR_{sd} \le 1,000)$ và vốn $M$ $(1 \le M \le 200,000)$, tìm mua bán tối ưu để lợi nhuận bán ngày cuối lớn nhất. Chỉ mua số cổ phiếu nguyên, không cần tiêu hết hay tiêu gì. Bảo đảm lợi nhuận không quá 500,000.

Ví dụ thị trường tăng, Bessie thích nhất: $S=2$, $D=3$, vốn đầu tư 10. Các cột là giá hôm nay, ngày mai, ngày kia.

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

Muốn lãi phải mua cổ phiếu 1 ngày 1. Bán ngày 2 rồi nhanh mua cổ phiếu 2: ngân hàng còn 4 và một cổ phiếu 2. Bán ngày cuối được 20, cộng ngân hàng tổng 24.

Dữ liệu vào

• Dòng 1: số nguyên $S$, $D$, $M$ cách nhau dấu cách.
• Dòng $2,\ldots,S+1$: dòng $s+1$ có $D$ giá $PR_{sd}$ cổ phiếu $s$ ngày $1,\ldots,D$.

Dữ liệu ra

• Dòng 1: số tiền tối đa sau bán ngày $D$.

Ví dụ

Dữ liệu vào 1

2 3 10
10 15 15
13 11 20

Dữ liệu ra 1

24

Tác giả: Rob Kolstad(?), 2008