测试数据来自 system/1649

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　小H发现了一个赚钱之道——经营游戏厅来赚取收益!

　　它打算用不超过 \(M\) 元钱去买一些游戏机，当然游戏机只是一个平台，因此还需要买游戏机对应的一些游戏！

　　市面上有 \(N\) 种游戏机，价格为 \(C_i\) ；第 \(i\) 种机上有 \(S_i\) 种游戏，其中第 \(j\) 种游戏的价格为 \(P_{i,j}\)，经营收益为 \(E_{i,j}\) 。如果想玩同一游戏机上的多种游戏，只要买一台游戏机和相应的游戏就够了。注意同一种游戏机或同一种游戏买两次不会产生双倍效益产生的。

　　现在请帮助小H算一算，它该选择买哪些游戏机和游戏，才能使收益之和最大？

【输入格式】

　　第一行：两个整数 \(N\) 和 \(M\)。它们的意义见题目描述。
　　第二行到第 \(N+1\) 行：第 \(i+1\) 行首先有两个整数 \(C_i\) 和 \(S_i\) ，其次有 \(S_i\) 对整数 \(P_{i,j}\) 和 \(E_{i,j}\)。它们的意义如题描述。

【输出格式】

　　一行一个整数，表示可以得到的最大收益。

【输入输出样例】

　Input

3 80
30 2 3 5 4 8
60 1 5 13
40 3 4 7 3 4 4 6

　Output

17

【输入输出样例解释】

　　购买第一种游戏机上的两种游戏，以及第三种第二种游戏，恰好花去 (30 + 3 + 4) + (40 + 3 ) = 80 元，收益为 (5 + 8) + 4 = 17。

【数据说明】

　　对于 \(30\%\) 的数据： \(1≤N≤10\)，\(1≤S_i≤10\)，\(1≤M≤1000\)
　　对于 \(60\%\) 的数据： \(1≤N≤50\)，\(S_i≤4\)，，\(1≤M≤100000\)
　　对于 \(100\%\) 的数据： \(1≤N≤50\)，\(1≤S_i≤10\)，\(1≤M,C_i,P_{i,j},E_{i,j}≤10^6\)

【来源】

　　Mr.he