d645: 輪下亡魂

出處

內容：

路過的鴨上次在你的幫忙之後，

成功解決鴨子王(duckingod)的難題而復活了！

但是有一天牠過馬路的時候…

牠因為闖紅燈結果被車撞死了囧

(…那有什麼辦法，鴨子又看不懂紅綠燈)

無奈的duckingod決定再給路過的鴨一次機會！

但是這次的題目比上次更難！

同樣是鴨飼料問題，限定的體積要吃得最飽，

但是現在除了普通的鴨飼料(只能吃一次)之外多了另外兩種神奇的飼料！

1.神的鴨飼料！不管被吃幾次都不會消失(吃到飽?)

2.分身鴨飼料！在一定次數內被吃幾次都不會消失

輸入說明：

每個測資點僅一組測資。

第一行有兩個正整數i,c代表飼料種類數、鴨子胃的容量，(1<=i<=1000 , 1<=c<=1000)

接下來i行每一行的飼料資料有三個正整數v,w,t，(1<=v<=10000,1<=w<=c,-1<=t<=100)

v是該飼料的飽足感、w是體積、t則代表飼料的類型：

t=-1表示是神的鴨飼料！

t=1表示是普通鴨飼料！

t>1表示是分身鴨飼料，可以被吃t次

輸出說明：

請輸出路過的鴨能取得的最大飽足感。

(答案保證不超過1000000000)

範例輸入：

7 100

2 4 -1

1 3 -1

60 10 1

40 10 1

10 10 3

5 6 7

6 5 2

範例輸出：

174

提示：

共計三個測資點，配分30％、35％、35％

出處：

jack1 (管理：jack1)