问题 4749 --3、魔法学习(magic)

4749: 3、魔法学习(magic)

题目描述

  卡卡西成功进入了阴影之门,也正式进入了世界魔法大学。她看见成千上万的学生穿着魔法袍,拿着魔法棒,骑着扫帚,在各种奇形怪状的教室间飞来飞去。这些学生有的在学习占星术,有的在学习变形术,有的在练习喷火术,真是让人目不暇接....!突然,卡卡西发现一个小姐姐愁眉苦脸的坐在墙角里走神,于是就不由自主的走上前去问道:“你好,我叫卡卡西,能在魔法大学里学习是多么幸福的事情呀,可是你为什么看起来不高兴呀?”,小姐姐擦了擦眼泪说:“我叫娜娜,今年在魔法大学念大一,主修魔法植物学,学习魔法需要买魔法书,而魔法书需要花钱买,但是我身上的金币不多了,怎么算都感觉不够,没法毕业了,呜呜.....”,卡卡西轻轻拍了拍她的肩膀:“娜娜姐姐别担心,我算术可厉害啦,你说说看,说不定有最优选择购买魔法书的方法呢,那样你就可以顺利毕业啦!”,“真的么,那谢谢你啦,听我介绍下情况....” 小姐姐说道。
娜娜在魔法学校进行学习,要想顺利毕业,必须要获得一定的效果值,而效果值是通过学习魔法获取的。魔法学校现有n个魔法,每个魔法分为若干个等级,第i个魔法有p问个等级,每个魔法学到每个等级都有一个效果值,当学习到第i个魔法的第j级后就可以获得的效果值为w[i][j], 魔法升一级需要一本魔法书, 购买魔法书需要金币,第i个魔法的每一级需要购买的魔法书的价格均相同,为c[i] (即第i个魔法每升一级都需要c[i]个金币),现在娜娜只有m个金币,且开始时娜娜所具有的效果值为0。
你的任务就是帮助娜娜利用现有的金币获得最大的效果值。

输入

输入数据共n+1行。第一行有两个正整数n和m (空格隔开),下面n行分别描述n个魔法,第i+1行描述第i个魔法格式如下句,p[i], w[i][1] ,w[i][2] ... w[i][p[i]] (第i个魔法的魔法书价格,第i个魔法的等级数,后面依次是学到每个等级后所获得的第i个魔法的效果值)。

输出

输出一个整数,即最大效果值。

样例输入输出

输入#1 复制
3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10
输出#1 复制
11

提示

样例解释:魔法学校有3个魔法,娜娜共有10个金币。第1个魔法的每一级的魔法书价格为1,共有3个等级,学习到每个等级后的效果值分别为: 1, 2, 2。(第1个魔法学到第一级需要1个金币,获得效果值为1,学到第二级需要2个金币,总的获得效果值为2,学到第三级需要3个金币,总的获得效果值为2。注意,此时虽然比第二级多花1个金币,但是获得的效果值却没有增加,依旧是2! 每个魔法的每个等级必须依次学习,不能越级,学习第二级之前必须先学完第一级,学习第三级之前必须先学完第一级和第二级)。第2个魔法的每一级的魔法书价格为2,共有3个等级,学习到每个等级后的效果值分别为: 2, 4,6。第3个魔法的每一级的魔法书价格为3,共有3个等级,学习到每个等级后的效果值分别为: 2, 1, 10 。在这种情况下要想获得最大的效果值,则要选择第1个魔法学习到第一级,花费1个金币,获得效果值1; 第2个魔法不学习; 第3 个魔法学习到第三级,花费9个金币,获得效果值10。总的获得效果值为11。

数据范围: 
0<n≤100, 0<m≤500, 0<p[i]≤ 50,0<c[i]≤10, w[i][j]可能为 负整数。保证输入数据和最终结果在longint 范围内。

序号 标题 作者 发表时间 费用 订购数 操作