题目描述

这天老师安排了n组工作让小光完成，时间为T，每个工作组中有m个工作，每一组工作有个分类值为s，如s是0表示组内至少要做一件工作，如s是1表示组内最多做一件工作，s是2表示组内工作随意完成，每项工作均有需花费的时间和获得的快乐值，求小光在T时间内可获得的最大快乐值。

输入格式

有多组测试数据，每组数据第一行有两个整数n和T(0≤n，T≤100)，表示有n组工作和时间T。随后是n组描述，每组两个数字（0＜m≤100）和s，表示该组工作有m个工作和该组工作的分类值。 随后是m对数字ci​，gi​（0≤ci​，gi​≤100），表示完成该工作需要的时间和获得的快乐值。 注意一个工作只能做一次。

输出格式

输出一个数，即获得的最大快乐值。若不能完成，则输出“-1”。

样例

输入复制

3 3　
2 1　2 53 8
2 01 0　2 1
3 2　4 32 11 1

输出复制

5