分组背包 (bag.cpp) Problem Describe 商场内有 n 件物品，每件物品有四个参数，对于第 i 个物品，我们用 v i 表示其价值，w i 表示其重量，t i 表示其类型，p i 表示其数量，注意：当 p i = 0 时表示第 i 件物品有无数个，p i > 0 时表示第 i 件物品有 p i 个 由于某种原因，你可以在商场里免费选购这些物品的若干件，但是对于同一类型的物品，你只能采购一种 （但是数量没有限制） ，比如有三件商品，如果用 (v,w,t,p) 来描述一件商品的四个参数，则两件商品的参数分 别为 (3,1,1,3),(7,2,1,1)，则在选择物品重量之和小于 4 的条件下你应该选择第一个商品 (3,1,1,3) 三件，总 价值为 9，但是虽然第一个商品 (3,1,1,3) 两件加上第二个商品 (7,2,1,1) 一件可以达到 13 的价值和，但是 他们是同一组的，你只能选择购买一种，不能两种都买 给出 m，求在满足上述条件以及总重量之和不超过 m 的条件下能买到的商品价值和的最大值
Input Describe
输入共一行
第一行两个正整数 n,m
接下来 n 行，每行四个整数 v i ,w i ,t i ,p i ，描述一件商品
Output Describe
输出共一行一个正整数，表示能买到的商品价值和的最大值
Sample Input
2 4
3 1 1 3
7 2 1 1
Sample Output
9
Data Size
对于所有数据:
1 ≤ n ≤ 400,1 ≤ m ≤ 100000,1 ≤ v i ≤ 10000,1 ≤ w i ≤ m,1 ≤ t i ≤ n,0 ≤ p i ≤ m