题目描述

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

$\red{Bessie}$很有先见之明，她不仅知道今天$\red{S (2 <= S <= 50)}$只股票的价格，还知道接下来一共$\red{D(2 <= D <= 10)}$天的（包括今天）。 给定一个$\red{D}$天的股票价格矩阵$\red{（1 <= }$价格 $\red{<= 1000）}$以及初始资金$\red{M(1 <= M <= 200,000)，}$求一个最优买卖策略使得最大化总获利。

每次必须购买股票价格的整数倍，同时你不需要花光所有的钱（甚至可以不花）。这里约定你的获利不可能超过$\red{500,000}$。 考虑这个牛市的例子（这是$\red{Bessie}$最 喜欢的）。

在这个例子中，有$\red{S=2}$只股票和$\red{D=3}$天。奶牛有$\red{10}$的钱来投资。

今天的价格 $\red{| }$明天的价格 $\red{| | }$后天的价格股票$\red{| | | 1 10 15 15 2 13 11 20 }$

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

输入格式

第一行: 三个空格隔开的整数：$\red{S, D, M}$

第$\red{2..S+1}$行: 行$\red{s+1}$包含了第$\red{s}$只股票第$\red{1..D}$天的价格

输出格式

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

样例

输入样例

2 3 10
10 15 15
13 11 20

输出样例

24