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

---

【题目描述】

　　小H同学确信所有问题都有个多项式时间算法，为了证明，他决定自己去当一次旅行商，在上路之前，小H需要挑选一些在路上使用的物品，但他只有一个能装体积为 \(m\) 的背包。显然，背包问题对小H来说过于简单了，所以他希望你来帮他解决这个问题。

　　小H可以选择的物品有 \(n\) 样，一共分为甲乙丙三类：

　　1．甲类物品的价值随着你分配给他的背包体积变化，它的价值与分配给它的体积满足函数关系式，\(v(x) = A*x^2-B*x\)，\(x\) 表示分配给该物品的体积，为非负整数，\(A，B\) 是每个甲类物品的两个参数。注意每个体积的甲类物品只有一个。
　　2．乙类物品的价值 \(A\) 和体积 \(B\) 都是固定的，但是每个乙类物品都有个参数 \(C\)，表示这个物品可供选择的个数。
　　3．丙类物品的价值 \(A\) 和体积 \(B\) 也是固定的，但是每个丙类物品可供选择的个数都是无限多个。

　　你最终的任务是确定小H的背包最多能装有多大的价值上路。

【输入格式】

　　第一行两个整数 \(n，m\)，表示背包物品的个数和背包的体积；
　　接下来 \(n\) 行，每行描述一个物品的信息。第一个整数 \(x\)，表示物品的种类：
　　　　若 \(x\) 为 1 表示甲类物品，接下来两个整数 \(A,B\)，为 \(A\) 类物品的两个参数； 　　
　　　　若 \(x\) 为 2 表示乙类物品，接下来三个整数 \(A,B,C\)。\(A\) 表示物品的价值，\(B\) 表示它的体积，\(C\) 表示它的个数；
　　　　若 \(x\) 为 3 表示丙类物品，接下来两个整数 \(A,B\)。\(A\)表示它的价值，\(B\) 表示它的体积。

【输出格式】

　　仅一行为一个整数，表示小H的背包能装的最大价值。

【输入输出样例1】

　Input

1 0
1 1 1

　Output

0

【输入输出样例2】

　Input

4 10
2 1 2 1
1 1 2
3 5 2
2 200 2 3

　Output

610

【数据限制】

　　对于 \(50\%\) 的数据，只有乙和丙两类物品；
　　对于 \(70\%\) 的数据，\(0<n≤100\)，\(0<m≤500\)，\(0<A,B,C≤200\)；
　　对于 \(100\%\) 的数据，\(0<n≤100\)，\(0<m≤2000\)，\(0<A,B,C≤200\)。

【来源】

　　Mr.he