More happiness

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/32768 K (Java/Others)

Description

As you know, poor XMM has been dreaming to go to Happyvalley for a long time. The good news is that today her mom finally agreed to take her there this weekend!
In order to make her journey in Happyvalley happier, XMM bought a map of Happyvalley to design a good plan. Happyvalley has N scenic spots which are connected by roads. XMM found that there is exactly one path between each two spots.
XMM can start her journey from arbitrary scenic spot. Several minutes are required for her to walk from one end to the other end on each road. Also, she would spend X minutes for each spot she visit. However, many reasons, such as XMM’s mood, weather condition and so on, may alter X. So there are many possible values of X.
Mom told XMM that she would stay in Happyvalley for only P minutes. Given the information of Happyvalley and the total time P minutes, also, with the time X XMM guesses she would spend in each spot, can you tell XMM the maximum number of spots she may visit? Note that each spot should be counted only once.

Input

The first line of the input is T (no more than 10), which stands for the number of test cases you need to solve.
On the first line of each test case, there are two numbers, N (no more than 200) and P (no more than 2000000). The following N-1 lines state the roads in the form of “a b c” which means it takes XMM c minutes to walk from spot a to spot b or from b to a (1 <= a, b <= N, 1 <= c <= 10000).
Then an integer Q (no more than 10000) in a single line is the number of all possible value X may be. Each of the following Q lines gives a possible X (no more than 10000).

Output

For each test case Q+1 lines are expected.
The first line is in the format of "Case x:\n", where x is the case number counted from one.
The (i+1)-th line should be the maximum number of spots XMM could get based on each possible X.

Sample Input

3 3 10 1 2 2 2 3 1 3 10 2 4 6 15 1 2 2 1 3 1 2 6 3 5 3 5 3 4 3 4 1 2 3 100 4 2000000 1 2 1 1 3 1 1 4 1 1 1

Sample Output

Case 1: 1 3 2 Case 2: 5 4 3 0 Case 3: 4

Hint

zhouzeyong

Source

2010 ACM-ICPC Multi-University Training Con

提交代码