0004 - 忍者の派遣

ある忍者の流派では，依頼主のもとに忍者を派遣し，その成果に応じて報酬を受け取る仕組みになっている．

この流派には元老と呼ばれる忍者が一人存在し，元老以外の忍者はただ一人の上司をもつ．機密性と統率性のため，業務に関する指示は常に上司から部下に伝えられ，その他の方法で伝えることは許されない．今，あなたはある依頼主のために何人かの忍者を集めて派遣することにした．派遣する忍者には，忍者ごとに定まっている給与を支払わなければならないが，支払う給与の合計値は一定の金額以下に抑えなく てはならない．また，指示を送るために責任者を一人選ばなければならず，責任者は派遣される忍者全てに指示を送れる必要がある．ただし，指示を送るさいには，派遣されない忍者がその指示を仲介しても構わない．また，責任者自身は派遣されてもされなくてもよく，派遣されなかった場合には給与は支払われない．

あなたは，予算の範囲内で，できるだけ依頼主の満足度を高める必要があると考えた．依頼主の満足度は，派遣された忍者の合計数に，責任者のリーダーシップを掛けた数になると考えられる．リーダーシップは，忍者ごとに定まっている数値である．

課題

それぞれの忍者 i (1 ≦ i ≦ N) の上司 B_i と派遣した場合の給与 C_i とリーダーシップ L_i，そして給与として使用できる予算額 M が与えられた時，条件を満たすように責任者・派遣される忍者を選ぶときの，顧客満足度のとりうる最大値を答えるプログラムを作成せよ．

制限

入力

標準入力から以下の入力を読み込め．

• 1 行目には整数 N, M が空白を区切りとして書かれている．N は人数を，M は予算をそれぞれ表す．
• 続く N 行には，各忍者の上司・給与・リーダーシップが書かれている．i + 1 行目には 3 つの整数 B_i, C_i, L_i が空白を区切りとして書かれている．これは，忍者 i の上司が忍者 B_i，派遣に必要な給与が C_i であり，リーダーシップが L_i であることを表す．B_i が 0 の時，忍者 i は元老であることを表す．B_i < i であることから，ある忍者の上司は必ずその忍者の番号より若い番号を持つ．

出力

標準出力に，顧客満足度の最大値をあらわす整数を 1 行で出力せよ．

採点基準

採点用データのうち，
配点の 30% 分については，N ≦ 3 000 を満たす．

入出力の例

入力例1

5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

出力例1

6

この場合，忍者 1 を責任者にし，忍者 3, 4 を派遣すると，必要な給与の合計は 4 なので，予算額である4 以下に収まる．このとき，参加人数は 2 人で，責任者のリーダーシップは 3 なので，顧客満足度は 6 となり，これが最大である．