奶牛虽天生谨慎，却在住房抵押贷款市场遭受重创，现在转而尝试股票。幸运的是 Bessie 能预知未来，不仅知道今天 $S$ $(2 \le S \le 50)$ 种股票的价格，还知道总共 $D$ 天 $(2 \le D \le 10)$ 的未来价格。

给定各天当前和未来价格的矩阵 $(1 \le PR_{sd} \le 1,000)$ 及初始资金 $M$ $(1 \le M \le 200,000)$，选择最优买卖策略，使最后一天卖出后的收益最大。只能买整数股，无须用完资金，甚至可以完全不花。保证获利不可能超过 500,000。

考虑下例 Bessie 最爱的牛市（上涨市场）：$S=2$ 种股票，$D=3$ 天，奶牛有 10 资金投资。表中各列是今天、明天、后天的价格：

                   Today's price
                   |   Tomorrow's price
                   |   |  Two days hence
             Stock |   |  | 
              1    10 15 15
              2    13 11 20

要赚钱，第一天必须买股票 1。第二天卖出，马上买股票 2，此时银行有 4，持有股票 2 一股。最后一天卖出得到 20，加上银行的 4，共 24。

输入格式

• 第 1 行：空格分隔的三个整数 $S$、$D$、$M$。
• 第 $2,\ldots,S+1$ 行：第 $s+1$ 行包含股票 $s$ 在第 $1,\ldots,D$ 天的 $D$ 个价格 $PR_{sd}$。

输出格式

• 第 1 行：第 $D$ 天卖出后能拥有的最大资金。

样例

输入格式 1

2 3 10
10 15 15
13 11 20

输出格式 1

24

题目作者：Rob Kolstad(?)，2008