13811381 SUSTech Online Judge
Problem 1381 --Pear tree

1381: Pear tree

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

Description

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).

Input

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)

Output

Each line outputs the maximum number of pears for each test case.


Sample Input

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

Sample Output

2
11

HINT

Source

 

[Submit][Status]