题目描述

尽管奶牛们天生谨慎，她们仍然在住房抵押信贷市场中受到打击，现在她们开始着手于股市。 Bessie 很有先见之明，她不仅知道今天 $s$ 只股票的价格，还知道接下来一共 $d$ 天的（包括今天）。给定一个 $d$ 天的股票价格矩阵以及初始资金 $m$，求最优买卖策略使得总获利最大化。每次必须购买股票价格的整数倍，同时你不需要花光所有的钱（甚至可以不花）。考虑这个牛市的例子（这是 Bessie 最喜欢的）。在这个例子中，有 $2$ 只股票和 $3$ 天。奶牛有 $10$ 的钱来投资。

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

输入格式

第一行：三个空格隔开的整数：$s,d,m$。

第 $2\sim s+1$ 行：第 $i+1$ 行包含了第 $i$ 只股票第 $1$ 至 $d$ 天的价格 $w_{i,{1\sim d}}$。

输出格式

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

2 3 10
10 15 15
13 11 20

24

数据规模与约定

对于 $100\%$ 的数据，$2 \leq s \leq 50$，$2 \leq d \leq 10$，$1 \leq m \leq 2\times10^5$，$1\leq w_{i,{1\sim d}}\leq 1000$。

约定你的获利不超过 $5\times10^5$。

题目来源

Usaco 2009 Feb Gold