2019 T3 纪念品

主知识点：动态规划。交叉标签：动态规划、完全背包、贪心。
暴力标注：DP 可用暴力拿部分分。
OJ 使用标准输入与标准输出。原比赛文件名为 souvenir.in / souvenir.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 256 MiB；测试点 20；总分 100。
数据来源：官网数据；与公开存档逐文件一致。

题目描述

已知未来 $T$ 天、$N$ 种纪念品的价格。初始有 $M$ 枚金币，没有纪念品。每天可按当天价格不限次数地买卖，每次购买须有足够现金，卖出的金币可立即使用，当日购买也可卖出。可以跨天持有，但必须在第 $T$ 天卖出全部纪念品。求最后能拥有的最多金币。

输入格式

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

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

输出格式

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

样例

样例 1

输入：

6 1 100
50
20
25
20
25
50

输出：

305

样例 2

输入：

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

输出：

217

数据范围与特殊性质

对于 $10\%$ 的数据，$T = 1$。

对于 $30\%$ 的数据，$T \leq 4, N \leq 4, M \leq 100$，所有价格 $10 \leq P_{i,j} \leq 100$。

另有 $15\%$ 的数据，$T \leq 100, N = 1$。

另有 $15\%$ 的数据，$T = 2, N \leq 100$。

对于 $100\%$ 的数据，$T \leq 100, N \leq 100, M \leq 10^3$，所有价格 $1 \leq P_{i,j} \leq 10^4$，数据保证任意时刻，小伟手上的金币数不可能超过 $10^4$。

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

DP 可用暴力拿部分分。枚举各纪念品持有数量、现金与逐日买卖方案，用去重避免同日无收益循环；T≤4、N≤4、M≤100、价格≥10 的 30% 是可尝试范围。另 T=1 直接输出 M，N=1 可单独按涨跌处理。不能用单品收益率贪心代替多品背包。

目标范围：小规模 30% 可尝试；T=1 为 10%。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P5662
• 赛事：CSP-J 第二轮入门级 2019。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。