C.葉精靈的果實

題目敘述

在經過一點小騷動後，皮卡丘一行人終於跟所有的伊布打好關係了。此時，外出的葉精靈帶著許多的樹果回到了伊布之家，要把這些樹果分享給所有的神奇寶貝。不過家中盛放樹果的盤子有重量的限制，如果這個盤子上放了超過限重的樹果，盤子就會被樹果的壓碎，而伊布們也只有這一個盤子，他們很講究一起吃東西時一定要放在這盤子上，象徵著彼此合作的精神。

不過值得注意的是伊布們對於食物的喜好程度有所不同，比如說他們比較喜歡吃橘子，但對於蘋果有點反感，因為蘋果對他們來說太硬了。於是他們對於每種食物都訂出了喜好的程度。為了能讓訪客們能真正體會伊布之家的飲食，他們希望今天放在盤子上的食物喜好的程度之總和能越大越好，代表他們心意。

不過樹果的種類有點多，看的大伙眼花撩亂，一直搞不定要擺放多少才好，你能協助他們完成分配嗎？

輸入說明

每次只會輸入一筆測資。
測資第一行有兩個數字$K,P$，代表葉精靈帶回了$K$種樹果、使用的盤子限重$P$單位。再接下來有$K$行，為每種樹果的資訊，每行行$i$有3個數字$N,F,W$，分別為第$i$種樹果的數量，喜好程度，每個樹果的重量。

已知在所有資料中，$K\leq 100$、$P\leq 1000000$、$\Sigma N\leq 1000000$、$F\leq 50$、$W\leq P$。

輸出說明

請輸出再限重條件下，食物喜好的程度之總和最大值。

範例輸入

3 10 3 5 3 3 7 6 1 10 9

範例輸出

15

配分方法

0% 範例資料
30% $\Sigma N\leq 10$
70% $\Sigma N\leq 100,P\leq 10000$
90% $K\leq 50,\Sigma N\leq 10000,P\leq 10000$
100% $K\leq 50,\Sigma N\leq 1000000,P\leq 500000$

Judge Setting

run-time limit: 300 ms
memory limit: 6553600 byte
測資數量: 0