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

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

3 10
1 3 1 2 2
2 3 2 4 6
3 3 2 1 10

11