描述

夏天近了，又到了恋爱的季节，小Q家门前的苹果树上结满了红红圆圆的苹果。

这株苹果树是一个有着\(n\)个结点的有根树，其中结点被依次编号为\(1\)至\(n\)。\(1\)号结点为根，其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果，第\(i\)个结点上有\(a_i\) (\(a_i > 0\))个苹果，每取走其中一个苹果就可以得到\(v_i\) (\(v_i > 0\))的幸福度（若在这个结点取走\(y\times a_i\)个苹果，则可以收获\(y\times v_i\)的幸福度）。如果在一个结点取走了至少一个苹果，则必须要在其父结点处取走至少一个苹果。

现在，给定正整数\(k\)，请从树上取走若干苹果。如果总计取走了\(t\)个苹果，且所有取了至少一个苹果的那些结点的最大深度为\(h\)（这里规定根结点的深度为\(1\)），则要求\(t-h\le k\)。问最大可以收获多少的幸福度？（这些幸福度全都归属于恋爱中的小Q。）

格式

输入格式

本题有多组测试数据，输入的第一行给定整数\(Q\)表示有\(Q\)组数据。之后依次给出\(Q\)组数据。

对于每一组数据来说，第一行包含两个整数\(n\) 和\(k\)。
之后\(n\)行，每行给出三个整数，描述了每一个结点。其中第\(i\)行的第一个整数给出了\(i\)的父结点标号（如果\(i = 1\)，则其父结点为\(0\)），第二个整数为\(a_i\)，第三个整数为\(v_i\)。

输出格式

输出一共有\(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

限制

有10%的数据，满足\(nk\le 3000000\)且给定的树的高度为\(2\)。

有20%的数据，满足\(nk\le 25000000\)且给定的树的高度为\(2\)。

有20%的数据，满足\(nk\le 25000000\)且所有\(a_i\)均为\(1\)。

还有20%的数据，满足\(nk\le 3000000\)，没有上述额外限制。

对于100%的数据，满足\(1\le Q\le 5\); \(1\le n\le 20000\); \(1\le k\le 500000\); \(1\le nk\le 25000000\); \(1\le a_i\le 10^8\); \(1\le v_i\le 100\)。

来源

SDOI 2017 Round2 Day1