1616 . 猴子點技能
Description
在未來的加強版中，原本的兩條技能購買路線變成了樹狀的了(當然，純屬虛構)! 一隻飛鏢猴可以實現至多 N 種 技能，對於一種技能，需要花費 C_i 元購買，而且它可能有依賴技能 P_i ，若 P_i 是 0，表示不需要先購買任何前置技能就可以購買這個技能；否則的話必須要先購買技能 P_i 才能夠買技能 i。技能的編號是 1 到 N。
對於每一種技能你都有喜好程度 L_i，請找一種總花費不超過 K 元的購買技能方案，使得在該方案底下你所購買的技能其喜好程度總和最大。
Input Format
第一行有一個正整數 T，表示接下來有幾筆測試資料(T<=100)。
對於每一筆測試資料，第一行有兩個整數 N, K(1<=N<=103, 0<=K<=105)。
接下來有 N 行，每一行有三個整數依序是 P_i, C_i, L_i(0<=P_i< i, 1<=C_i<=105, 1<=L_i<=106)。
Output Format
對於每一筆測試資料，請輸出預算範圍內最大的喜好程度總和。
Sample Input 1
1 3 10 0 4 7 1 4 8 1 5 9
Sample Output 1
16
Hints
對於範例測資，選1, 3這兩種技能。
Problem Source
Migrated from old NTUJ.
Subtasks
| No. | Testdata Range | Score |
|---|