Problem Description
There is a rooted tree with n nodes. For each node i, there is an item whose volume is ci and value is vi and if node i is not the root, it is guaranteed that |subtreei|≤23|subtreefatheri|.Bacon wants to pick items in subtrees so that their total volume is exactly t. Help Bacon determine the maximal total value of items he can pick.
Input
The first line contains one integer T(1≤T≤40) and there are exactly T test cases below.
For each test case, the first line contains one integer n (1≤n≤2×104).
The following n - 1 lines describe edges in the tree. Each line contains two integers ai and bi(1≤ai,bi≤n,ai≠bi) describing an edge of the tree.
For the following n lines, the i-th line contains two integers ci and vi(1≤ci≤5,1≤vi≤109).
Next line contains one integer the number of queries Q and each of the following Q lines contains two integers si and ti(1≤si≤n,1≤ti≤105) as a query.
Note that node 1 is the root of the tree.
There is no more than 4 test cases that n is greater than 104, and no more than 10 test cases that n is greater than 103. sum of all Q are not greater than 2×105.
Output
For each test case, first line contains "Case #x:", where x indicates the number of test cases (starting from 1).
Then print Q lines and the i-th line contains the answer of the i-th query. Print -1 for the query if there is no way to pick items in subtrees with total volume t.
Sample Input
2
5
1 2
1 3
1 4
1 5
1 1
2 2
3 3
4 4
5 5
3
1 15
2 2
3 3
5
1 2
1 3
1 4
4 5
5 123
3 4543
4 21
1 1231
2 12
3
1 5
5 2
4 4
Sample Output
Case #i：
15
2
3
Case #2:
4555
12
-1
