There is a pear tree with pears on the edge of the tree. Xiao Ming wants to keep k edges, which means to subtract other edges. Xiao Ming hopes to keep the most pear on the reserved edge. Please help Xiao Ming.
Note: The reserved edge must be connected to the root.(The root is 1).
The first line is the number of test T(1<=T<=1e3)
For each test:
There are two integers in the first line n,k (2<=n<=100, 1<=k<n)
The next n-1 lines: i-th line have two integers ai, bi.
ai means: i+1 connect with ai
bi means: the number of the bear on the edge between ai and i+1.
(1<=ai<=n, 0<=bi<=1e5)
Each line outputs the maximum number of pears for each test case.
2
3 1
1 2
2 10
5 2
1 5
1 6
2 4
3 32
11