题目描述

你正在玩一个名叫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

题目来源

没有写明来源