Cointree(II)
描述
小k有一颗金币树。
这株coin树是一个有着n个结点的有根树，其中结点被依次编号为1至n。
1号结点为根，其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些金币袋，第i个结点上有ai(ai>0)个金币袋，每取走其中一个金币袋就可以得到vi (vi>0)的金币（若在这个结点取走y*ai个金币袋，则可以收获y*vi的金币）。如果在一个结点取走了至少一个金币袋，则必须要在其父结点处取走至少一个金币袋。
现在，给定正整数k，请从树上取走若干金币袋。如果总计取走了t个金币袋，且所有取了至少一个金币袋的那些结点的最大深度为ℎ（这里规定根结点的深度为1），则要求t−h≤k。问最大可以收获多少的金币？（这些金币全都归属于集币中的小k。）
格式
输入格式
本题有多组测试数据，输入的第一行给定整数Q表示有Q组数据。之后依次给出Q组数据。
对于每一组数据来说，第一行包含两个整数n和k。
之后n行，每行给出三个整数，描述了每一个结点。其中第i行的第一个整数给出了i的父结点标号（如果i=1，则其父结点为0），第二个整数为ai，第三个整数为vi;
输出格式
输出一共有Q行，对应了Q组数据。
对于每一组数据，输出一个整数，表示最大可以收获的金币。
样例1
样例输入1

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

样例输出1

15
316

*数据范围限制
对于100%的数据，满足1≤Q≤20; 1≤n≤20000;1≤k≤500000; 1≤n*k≤25000000;1≤ai≤100000000; 1≤vi≤100。

*时空限制
每个测试点5秒，1GB。

*来源
题目与测试数据::沈齐宸