文理学院程序设计在线练习


Anying's Morning Jogging

Time Limit: 10 Second(s)    Memory Limit: 32 MB

Total Submission(s): 3   Accepted Submission(s): 0
Problem Description

Anying is an otaku, feeling the body lack of exercise, so he want to keep running in the morning every day, then he need to design the running routes.
Anying plans to run between N places,and there are only N - 1 roads to connect these place and for simplicity, we assume that there is only one path to go from one city to another city.
We define two parameters here.Let X represents the minimal path’s length we need.We define another parameter Y,where Y is the number of paths which the length is no less than X.We assumes the path can not go through one place more than once and the path go from A place to B place equals to the path of B place to A place.
In this problem,we give you a number Z, your job is to calculate the maximum X which can guarantee the Y no less than Z.

Input

The first line is the number of test cases T(T<=20).
For each case,the first line contains two integers N and Z. The next N - 1 lines contain the descriptions of the roads. The i-th line contains two integers Pi,Wi,that mean that the i-th road connects vertex (i + 1) and Pi and has length Wi.
(1<N<=20000,0<Z<=100000000,0< <=100000)

Output

For each test case, output one line that contains an integer equals to the maximum X,if it not exist,output -1.

Sample Input
2
4 3
1 3
1 4
1 3
4 7
1 3
1 4
1 3
Sample Output
6
-1
Source

2014市赛