TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6412
  • 题目
  • P6412[CSP-J 2019]纪念品
    限制 : 时间限制 : 20000 MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

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

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

    1. 任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品
    2. 卖出持有的任意一个纪念品,以当日价格换回金币。

    每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当日卖出换回金币。当然,一直持有纪念品也是可以的。

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

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

    输入格式

    第一行包含三个正整数$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

    样例输出 1

    305

    样例输入 2

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

    样例输出 2

    217

    提示

    输入输出样例1说明

    最佳策略是:

    第二天花光所有100枚金币买入5个纪念品1;
    第三天卖出5个纪念品1,获得金币125枚;
    第四天买入6个纪念品1,剩余5枚金币;
    第六天必须卖出所有纪念品换回300枚金币第四天剩余5枚金币,共305枚金币。

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

    输入输出样例2说明

    最佳策略是:

    第一天花光所有金币买入10个纪念品1;
    第二天卖出全部纪念品1得到150枚金币并买入8个纪念品2和1个纪念品3,剩余1枚金币;
    第三天必须卖出所有纪念品换回216枚金币,第二天剩余1枚金币,共217枚金币。

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

    数据规模与约定

    对于10%的数据,\(T=1\)
    对于30%的数据,\(T\leq4,\quad N\leq4,\quad M\leq100\),所有价格$10\leq P_{i,j}\leq100$。
    另有15%的数据,\(T\leq100,\quad N=1\)
    另有15%的数据,\(T=2,\quad N\leq100\)
    对于100%的数据,\(T\leq100,\quad N\leq100,\quad M\leq10^3\),所有价格$1\leq P_{i,j}\leq10^4$,数据保证任意时刻,小明手上的金币数不可能超过$10^4$。