暂无测试数据。

【题目描述】

小X确信所有问题都有个多项式时间算法，为了证明，他决定自己去当一次旅行商，在上路之前，小X需要挑选一些在路上使用的物品，但他只有一个能装体积为m的背包。显然，背包问题对小X来说过于简单了，所以他希望你来帮他解决这个问题。
小X可以选择的物品有n样，一共分为甲乙丙三类：
①甲类物品的价值随着你分配给它的背包体积变化，他的价值与分配给它的体积（非负整数）满足函数关系式，v(x)=A*x^2-B*x,A,B是每个甲类物品的两个参数。甲类物品可以有若干个，但是同一个体积的物品只有一个。
②乙类物品的价值A和体积B都是固定的，但是每个乙类物品都有个参数C，表示这个物品可供选择的个数。
③丙类物品的价值A和体积B都是固定的，但是每个丙类可供选择的个数都是无限多个。
你最终的任务是确定小X的背包最多能装多大的价值上路。

【输入格式】

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

【输出格式】

一个数表示最大价值。

【输入样例】

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

【输出样例】

610

【数据范围】

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