#787. 纪念品

纪念品

题目描述

小伟突然获得一种超能力,他知道未来 T\red{T}N\red{N} 种纪念品每天的价格。某个纪念品的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。

每天,小伟可以进行以下两种交易无限次:

任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品; 卖出持有的任意一个纪念品,以当日价格换回金币。 每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当日卖出换回金币。当然,一直持有纪念品也是可以的。

T\red{T} 天之后,小伟的超能力消失。因此他一定会在第 T\red{T} 天卖出所有纪念品换回金币。

小伟现在有 M\red{M} 枚金币,他想要在超能力消失后拥有尽可能多的金币。

输入格式

第一行包含三个正整数 T,N,M\red{T, N, M},相邻两数之间以一个空格分开,分别代表未来天数 T\red{T},纪念品数量 N\red{N},小伟现在拥有的金币数量 M\red{M}

接下来 T\red{T} 行,每行包含 N\red{N} 个正整数,相邻两数之间以一个空格分隔。第 i\red{i} 行的 N\red{N} 个正整数分别为 Pi,1,Pi,2,,Pi,N\red{ P_{i,1}, P_{i,2}, \dots, P_{i,N } },其中 Pi,j\red{P_{i,j}} 表示第 i\red{i} 天第 j\red{j} 种纪念品的价格。

输出格式

输出仅一行,包含一个正整数,表示小伟在超能力消失后最多能拥有的金币数量。

输入样例1

6 1 100
50
20
25
20
25
50

输出样例1

305

输入样例2

3 3 100
10 20 15
15 17 13
15 25 16

输出样例2

217

提示

【输入输出样例 1\red{1} 说明】

最佳策略是:

第二天花光所有 100\red{100} 枚金币买入 5\red{5} 个纪念品 1\red{1}

第三天卖出 5\red{5} 个纪念品 1\red{1},获得金币125\red{125} 枚;

第四天买入 6\red{6} 个纪念品 1\red{1},剩余 5\red{5} 枚金币;

第六天必须卖出所有纪念品换回 300\red{300} 枚金币,第四天剩余 5\red{5} 枚金币,共 305\red{305} 枚金币。

超能力消失后,小伟最多拥有 305\red{305} 枚金币。

【输入输出样例 2\red{2} 说明】

最佳策略是:

第一天花光所有金币买入 10\red{10} 个纪念品 1\red{1}

第二天卖出全部纪念品 1\red{1} 得到 150\red{150} 枚金币并买入 8\red{8} 个纪念品 2\red{2}1\red{1} 个纪念品 3\red{3},剩余 1\red{1} 枚金币;

第三天必须卖出所有纪念品换回216\red{216} 枚金币,第二天剩余1\red{1}枚金币,共 217\red{217} 枚金币。

超能力消失后,小伟最多拥有 217\red{217} 枚金币。

【数据规模与约定】

对于 10%\red{10\%} 的数据,T=1\red{T = 1}

对于 30%\red{30\%} 的数据,T4,N4,M100\red{T \leq 4, N \leq 4, M \leq 100},所有价格 10Pi,j100\red{10 \leq P_{i,j} \leq 100}

另有 15%\red{15\%} 的数据,T100,N=1\red{T \leq 100, N = 1}

另有 15%\red{15\%} 的数据,T=2,N100\red{T = 2, N \leq 100}

对于 100%\red{100\%} 的数据,T100,N100,M103\red{T \leq 100, N \leq 100, M \leq 10^3},所有价格 1Pi,j104\red{1 \leq P_{i,j} \leq 10^4},数据保证任意时刻,小明手上的金币数不可能超过 104\red{10^4}