题目描述

有 $n$ 种物品要放到一个袋子里，袋子的总容量为 $m$。

物品一共有 $3$ 类，第 $i$ 种物品属于第 $a_i$ 类，它的体积为 $v_i$，把它放进袋子里会获得 $w_i$ 的收益。

如果它属于第 $1$ 类物品，每种只能用一次。

如果它属于第 $2$ 类物品，每种可以用无限多次。

如果它属于第 $3$ 类物品，每种可以用 $l_i$ 次。

问如何选择物品，使得在物品的总体积不超过 $m$ 的情况下，获得最大的收益？请求出最大收益。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行三到四个整数 $a_i,v_i,w_i$ 或 $a_i,v_i,w_i,l_i$。

输出格式

一个整数，表示答案。

Samples

5 10
1 6 5
3 3 4 2
1 5 2
3 3 5 2
2 3 2

14

数据规模

对于所有数据保证 $1≤n,m,v_i,w_i,l_i≤1000,1≤a_i≤3$。