《算法竞赛宝典》基础算法艺术(公开课程)

【题目描述】(busy.cpp/c/pas)　HDU 3535

  　魔法世界历史上曾发生过多次大规模灭绝战争。例如疯狂屠杀世界人口约２亿人以至于荣登“吉尼斯世界纪录”的蒙帝国铁骑军，其幕后推手即是天顶星人。但在人类文明生死存亡之际，总会涌现出许许多多的英雄人物奋起抗争，拯救人民于水火之中。

现在，抵御天顶星人进攻的重任落在了魔法学院众师生的肩上。这天墨老师安排了n组工作让楚继光完成，时间为T，每个工作组中有m个工作，每一组工作有个分类值为s，如s是0表示组内至少要做一件工作，如s是1表示组内最多做一件工作，s是2表示组内工作随意完成，每项工作均有需花费的时间和获得的快(tong)乐(ku)值，求楚继光在T时间内可获得的最大快乐值。

【输入格式】

有多组测试数据，每组数据第一行有两个整数n和T (0≤n，T≤100)，表示有n组工作和时间T。随后是n组描述，每组两个数字m(0<m≤100)和s，表示该组工作有m个工作和该组工作的分类值。

随后是m对数字c_i，g_i (0≤c_i，g_i≤100)，表示完成该工作需要的时间和获得的快乐值。注意一个工作只能做一次。

【输出格式】

获得的最大快乐值。若不能完成，则输出“－1”。

【输入样例】

3 3　

2 1　2 5  3 8

2 0  1 0　2 1 

3 2　4 3  2 1  1 1

【输出样例】

5