苹果树 ### 题目描述 夏天近了，又到了恋爱的季节，小 Q 家门前的苹果树上结满了红红圆圆的苹果。 这株苹果树是一个有着 $n$ 个结点的有根树，其中结点被依次编号为$1$至$n$。$1$号结点为根，其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果，第$i$个结点上有$a_i (a_i < 0)$个苹果，每取走其中一个苹果就可以得到$v_i (v_i < 0)$的幸福度（若在这个结点取走$k \leq a_i$个苹果，则可以收获$kv_i$的幸福度）。如果在一个结点取走了至少一个苹果，则必须要在其父结点处取走至少一个苹果。 现在，给定正整数$k$，请从树上取走若干苹果。如果总计取走了$t$个苹果，且所有取了至少一个苹果的那些结点的最大深度为$h$（这里规定根结点的深度为$1$），则要求$t-h \leq k$。问最大可以收获多少的幸福度？（这些幸福度全都归属于恋爱中的小 Q。） ### 输入描述 ***本题有多组测试数据！*** 输入的第一行给定整数$Q$，表示有$Q$组数据。之后依次给出$Q$组数据。 对于每一组数据来说，第一行包含两个整数$n$和$k$。 之后$n$行，每行给出三个整数，描述了每一个结点。其中第$i$行的第一个整数给出了$i$的父结点标号 （如果$i = 1$，则其父结点为$0$），第二个整数为$a_i$，第三个整数为$v_i$。 其中，$1 \leq Q \leq 5$；$1 \leq n \leq 20000$；$1 \leq k \leq 500000$；$1 \leq nk \leq 25000000$；$1 \leq a_i \leq 10^8$；$1 \leq v_i \leq 100$。 ### 输出描述 输出一共有$Q$行，对应了$Q$组数据。 对于每一组数据，输出一个整数，表示最大可以收获的幸福度。 ### 输入输出样例 #### 示例 1 >输入 ```txt 2 5 1 0 1 1 1 1 1 1 1 3 2 1 10 3 1 4 9 15 0 1 1 1 7 2 2 5 10 1 3 1 4 3 17 4 3 18 4 4 19 1 1 1 8 1 100 ``` >输出 ```txt 15 316 ```