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