题目描述

HDU 3535

魔法世界历史上曾发生过多次大规模灭绝战争。例如，疯狂屠杀世界人口约$\red{2}$亿人以 至于荣登"吉尼斯世界纪录"的蒙帝国铁骑军,其幕后推手即是天顶星人。但在人类文明生 死存亡之际，总会涌现出许许多多的英雄人物奋起抗争，拯救人民于水火之中。 现在,抵御天顶星人进攻的重任落在了魔法学院众师生的肩上。这天墨老师安排了$\red{n}$ 组工作让楚继光完成,时间为$\red{T,}$每个工作组中有$\red{m}$个工作,每一组工作有个分类值为$\red{s,}$如 $\red{s}$是$\red{0}$表示组内至少要做一件工作,如$\red{s}$是$\red{1}$表示组内最多做一件工作,$\red{s}$是$\red{2}$表示组内工 作随意完成，每项工作均有需花费的时间和获得的快$\red{(tong)}$乐$\red{(ku)}$值,求楚继光在$\red{T}$时间 内可获得的最大快乐值。

输入格式

有多组测试数据,每组数据第一行有两个整数$\red{n}$和$\red{T (0≤}$$\red{n,T≤}$$\red{100),}$表示有$\red{n}$组工作 和时间$\red{T}$。随后是$\red{n}$组描述,每组两个数字$\red{m(0<m≤}$$\red{100)}$和$\red{s,}$表示该组工作有$\red{m}$个工作 和该组工作的分类值。 随后是$\red{m}$对数字$\red{ci,gi(0≤}$$\red{ci,gi≤}$$\red{100),}$表示完成该工作需要的时间和获得的快乐值。

注意一个工作只能做一次。

输出格式

获得的最大快乐值。若不能完成,则输出"$\red{-1}$"。

样例

输入样例

3 3
2 1  2 5  3 8
2 0  1 0  2 1
3 2  4 3  2 1  1 1

输出样例

5