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.