P2938 [USACO09FEB] Stock Market G

题目描述

贝西有内部消息，她知道 $S$ 只股票在今后 $D$ 天内的价格。

假设在一开始，她筹集了 $M$ 元钱，那么她该怎样操作才能赚到最多的钱呢？贝西在每天可以买卖多只股票，也可以多次买卖同一只股票，交易单位必须是整数，数量不限。举一个牛市的例子：

假设贝西有 $10$ 元本金，股票价格如下：

最赚钱的做法是：今天买入 $A$ 股 $1$ 张，到明天把它卖掉并且买入 $B$ 股 $1$ 张，在后天卖掉 $B$ 股，这样贝西就有 $24$ 元了。

输入格式

第一行：三个整数 $S,D$ 和 $M$，$2\le S\le 50,2\le D\le 10,1\le M\le 200000$。

第二行到第 $S + 1$ 行：第 $i + 1$ 行有 $D$ 个整数：$P_{i,1}$ 到 $P_{i,D}$，表示第 $i$ 种股票在第一天到最后一天的售价，对所有 $1\le j\le D$，$1\le P_{i,j}\le 1000$。

输出格式

单个整数：表示可以获得的最大钱数，保证这个数不会超过 $500000$。

输入输出样例 #1

输入 #1

2 3 10 
10 15 15 
13 11 20

输出 #1

24