经过多年的研究,伊库塔获得了预测未来的能力!他在这项研究上花费了大量的时间和金钱,但他终于得到回报的时候了。为了拿回自己的钱,伊库塔决定开始投资股票。
Ikta 目前没有股票, x 我有日元。他选择投资的股票是 n 从今天开始的类型和相关信息 d 成功预测每日股价。结果,令人惊讶的是,从今天开始 d 事实证明,盘中股价根本没有波动。换句话说,今天是第一天 i (1 \leq i \leq d) 日库存 j (1 \leq j \leq n) 股价 pi,j 我知道日元。 Ikta每天都可以自由买卖股票。也就是说,以下操作(购买/出售)可以在任何时间以任何顺序、任何次数执行。但每次操作前后持有的货币和股票单位数量必须是非负整数。 在
購入 : i 日,股票类型 j (1 \leq j \leq n)并选择一个 pi,j 支付日元购买 1 单位库存 获取 j 。
売却 : i 日,股票类型 j (1 \leq j \leq n)并购买 1 单位股票。 支付 j 支付 pi,j 获取日元。
(在他埋头研究的同时,证券交易系统取得了长足的进步,不再收取交易费用。)
伊克塔在大学学习的是信息科学,但他忘记了大学所学的一切,全身心投入到未来的预测研究中。我希望你为他编写一个程序,以最大化他在最后一天所拥有的金钱。
输入
输入按以下格式给出。
n d x
p1,1 ... p1,n
...
pd,1 ... pd,n
n : 股份类型数量
d : 日数
x :第一天持有的资金
pi,j : i 当日库存j股价(今天是第一天)
约束
输入中的每个变量都是满足以下约束的整数。
1 \leq n \leq 10
1 \leq d \leq 10
1 \leq x, pi,j \leq 105
您最后一天拥有的钱是 105 保证:
输出
如果您进行最佳投资,则在一行中输出您最后一天拥有的金额。
示例输入 1
2 2 5 3 2 5 4
样本输入 1 的输出
9
例如,每只股票买入一份。
示例输入 2
1 2 5 6 10000
样本输入 2 的输出
5
不允许小于 1 单位的交易。这就是中小投资者的悲哀。
示例输入 3
2 3 5 4 5 6 3 8 5
样本输入 3 的输出
11
第一天投资第一类股票,第二天投资第二类股票。
示例输入 4
3 3 10 10 9 6 8 7 3 7 5 1
样本输入 4 的输出
10
有时经济不好。