Problem E: Pear tree

Problem E: Pear tree

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 25  Solved: 6
[Submit][Status][Web Board]


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.

Sample Input

3 1
1 2
2 10
5 2
1 5
1 6
2 4
3 3

Sample Output