题目描述

卡卡西成功进入了阴影之门，也正式进入了世界魔法大学。她看见成千上万的学生穿着魔法袍，拿着魔法棒，骑着扫帚，在各种奇形怪状的教室间飞来飞去。这些学生有的在学习占星术，有的在学习变形术，有的在练习喷火术，真是让人目不暇接呀……！突然，卡卡西发现一个小姐姐愁眉苦脸地坐在墙角里走神，于是就不由自主地走上前去问道：“你好，我叫卡卡西，能在魔法大学里学习是多么幸福的事情呀，可是你为什么看起来不高兴呀？”
小姐姐擦了擦眼泪说：“我叫娜娜，今年在魔法大学念大一，主修魔法植物学，学习魔法需要买魔法书，而魔法书需要花钱买，但是我身上的金币不多了，怎么算都感觉不够，没法毕业了，呜呜……”
卡卡西轻轻拍了拍她的肩膀：“娜娜姐姐别担心，我算术可厉害啦，你说说看，说不定有最优选择购买魔法书的方法呢，那样你就可以顺利毕业啦！”
“真的么，那谢谢你啦，听我介绍下情况……” 小姐姐说道。

题目背景

娜娜在魔法学校进行学习，要想顺利毕业，必须要获得一定的效果值，而效果值是通过学习魔法获取的。魔法学校现有$n$个魔法，每个魔法分为若干个等级，第$i$个魔法有$p[i]$个等级，每个魔法学到每个等级都有一个效果值。当学习到第$i$个魔法的第$j$级后，可以获得的效果值为$w[i][j]$。魔法升一级需要一本魔法书，购买魔法书需要金币，第$i$个魔法的每一级需要购买的魔法书的价格均相同，为$c[i]$（即第$i$个魔法每升一级都需要$c[i]$个金币）。现在娜娜只有$m$个金币，且开始时娜娜所具有的效果值为$0$。

你的任务就是帮助娜娜利用现有的金币获得最大的效果值。

输入格式

输入数据共$n+1$行。
第一行有两个正整数$n$和$m$（空格隔开）。
下面$n$行分别描述$n$个魔法，第$i+1$行描述第$i$个魔法，格式如下：
$c[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

解释#1

魔法学校有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。

数据范围

40% 数据 n<=10

$0 < n \leq 100$，$0 < m \leq 500$，$0 < p[i] \leq 50$，$0 < c[i] \leq 10$，$w[i][j]$可能为负整数。保证输入数据和最终结果在int范围内。 复制