#4457. 游戏任务

内存限制:64 MiB 时间限制:10 Sec

题目描述

你正在玩一个名叫Age Of Cities的游戏。由于迫切需要升级你的城市,而且因为你太笨了,只知道做任务可以增加经验值,所以你决定去做游戏任务。你使用了一种顶尖的黑客技术得到了整个游戏的任务描述,发现这个游戏的任务可以分成主任务和附属任务两种,而你只有在完成主任务后才能解锁该主任务下的附属任务。你快速估计了一下你完成每个任务所需要的时间,并了解了完成这个任务可以增加的经验值,而经验值正是你升级所必须的。然而留给你的时间不长了,因为你的暑假只剩下 个小时了,而暑假过后你打算要好好学习,再也不会玩游戏了。所以你希望能够在这有限的 小时内获得最大的经验值。你整理出了做每个任务需要的时间 和做每个任务能够获得的经验值 ( 的单位为小时且保证 和 都是整数),然而你并不关心应该做什么样的任务,你只关心自己能得到的最大的经验值是多少。(我们假设你能够一天24小时不睡觉不吃饭不上厕所,全部用来玩游戏)

输入格式

输入的第一行是两个整数n,T,表示主任务的数目以及剩余的时间;
接下来的输入描述了这n个主任务。对于每个主任务,第一行为三个整数n_i,t_i0,c_i0,表示第i个主任务下有n_i个附属任务,且完成主任务所需的时间为t_i0,得到的经验值为c_i0;接下来n_i行,每行两个整数t_ij,c_ij,表示第i个主任务下的第j个附属任务所需的时间为t_ij,得到的经验值为c_ij。

输出格式

输出一行,包含一个整数,表示可以获得的经验值的最大值。

样例

样例输入


			
3 10
0 2 3
0 3 6
0 5 8

样例输出


			
17

数据范围与提示

1≤n≤100,0≤n_i≤500,1≤t_ij,T≤500,1≤c_ij≤100,000