← 返回题目列表

AtCoder · icpc2013summer_day3_a

A. 投资大师

中文机器翻译题面 查看原题

经过多年的研究,伊库塔获得了预测未来的能力!他在这项研究上花费了大量的时间和金钱,但他终于得到回报的时候了。为了拿回自己的钱,伊库塔决定开始投资股票。

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
  • 有时经济不好。