J17 实践-5 股神之路

题目描述

佩奇在模拟人生里，又有金钥匙开启了她的股神之路！她通过特殊的手段，知道了今天 $S$ 只股票的价格，还知道接下来一共 $D$ 天的（包括今天）。 现在给定一个 $D$ 天的股票价格矩阵（$1 \leq$ 价格 $\leq 1000$）以及初始资金 $M$ ，求一个最优买卖策略使得最大化总获利。每次必须购买股票价格的整数倍，同时不需要花光所有的钱（甚至可以不花）。同时约定获利不可能超过 $500,000$。 在这个例子中，有 $S=2$ 只股票和 $D=3$ 天。佩奇有 $10$ 的钱来投资。

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

输入格式

第一行：三个空格隔开的整数：$S, D, M$； 第 $2..S+1$ 行: 行 $S+1$ 包含了第 $S$ 只股票第 $1..D$ 天的价格。

输出格式

一个数字，最后一天卖掉股票之后最多可能的钱数。

样例输入

2 3 10
10 15 15
13 11 20

样例输出

24

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$2 \le S \le 50; 2\leq D \leq 10;1 \leq M \leq 200,000$。