题目描述

$\red{As is known to all，}$$\red{WZK }$很能吃小鸡腿，但他的胃毕竟有一个最大容纳值 $\red{c，}$否则为 胃中小鸡腿的巨大引力场和 $\red{lōng }$场叠加后会有很可怕的效果。

在 $\red{CZYZ }$的食堂一共有 $\red{n }$种小 鸡腿有卖，每种小鸡腿都有有限的个数、重量和让 $\red{WZK }$感到的满意度。$\red{WZK }$想在肚子不被撑 爆的前提下，取得最大的满意度值。

然后 $\red{lōng }$场就得到了大大的 $\red{power up}$。

输入格式

第一行：两个正整数 $\red{n,c}$。

接着 $\red{n }$行，每行三个正整数 $\red{Ai,Mi,Wi,}$分别表示每种小鸡腿的个数、重量和满意度。

输出格式

一个正整数，表示最大的满意度。

样例

输入样例

3 10
2 1 3
1 5 8
3 3 5

输出样例

19

提示

数据限制:

$\red{20\%}$的数据$\red{∑Ai<=25}$

另外 $\red{30\%}$的数据 $\red{c<=1000, }$$\red{∑Ai<=10000}$

对于 $\red{100\%}$的数据 $\red{c<=10000,n<=100,Ai<=1000}$