题目描述

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

娜娜在魔法学校进行学习，要想顺利毕业，必须要获得一定的效果值，而效果值是通过学习魔法获取的。魔法学校现有$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。

数据范围

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