[Usaco2009 Feb]Stock Market 股票市场

尽管奶牛们天生谨慎，她们仍然在住房抵押信贷市场中受到打击，现在她们开始着手于股市。

Bessie 很有先见之明，她不仅知道今天 $S$ 只股票的价格，还知道接下来一共 $D$ 天（包括今天）的价格。

给定一个 $D$ 天的股票价格矩阵以及初始资金 $M$ ，求一个最优买卖策略使得总获利最大化。每次必须购买股票价格的整数倍（即只能买整数股），同时你不需要花光所有的钱（甚至可以不花）。这里约定你的获利不可能超过 $500000$ 。

考虑这个牛市的例子（这是 Bessie 最喜欢的）。在这个例子中，有 $S=2$ 只股票和 $D=3$ 天，奶牛有 $10$ 的钱来投资：

股票	今天的价格	明天的价格	后天的价格
$1$	$10$	$15$	$15$
$2$	$13$	$11$	$20$

以如下策略可以获得最大利润：第一天买入第一只股票；第二天把它卖掉（得到 $15$ ）并且迅速买入第二只（花费 $11$ ），此时还剩下 $4$ 的钱；最后一天卖掉第二只股票，此时一共有 $4+20=24$ 的钱。

输入格式

第一行：三个空格隔开的整数 $S, D, M$ 。

第 $2\sim S+1$ 行：第 $s+1$ 行包含了第 $s$ 只股票第 $1\sim D$ 天的价格。

第一行：最后一天卖掉股票之后最多可能的钱数。

2 3 10
10 15 15
13 11 20

即题目描述中给出的牛市例子，最终持有 $24$ 的钱。

本题为 USACO 2009 Feb 试题「Stock Market 股票市场」，题面与测试数据整理自 BZOJ 1578。

2 3 10
10 15 15
13 11 20