There is a rooted tree with n nodes. For each node i, there is an item whose volume is $c_i$ and value is $v_i$ and if node i is not the root, it is guaranteed that $|subtreei| \leq \frac{2}{3}|subtree_{father_i} |$.Bacon wants to pick items in $subtree_s$ so that their total volume is exactly t. Help Bacon determine the maximal total value of items he can pick.
The first line contains one integer T($1 \leq T \leq 40$) and there are exactly T test cases below.
For each test case, the first line contains one integer n ($1 \leq n \leq 2 \times 10^4$).
The following n - 1 lines describe edges in the tree. Each line contains two integers $a_i$ and $b_i (1 \leq a_i,b_i \leq n,a_i \neq b_i)$ describing an edge of the tree.
For the following n lines, the i-th line contains two integers $c_i$ and $v_i (1 \leq c_i \leq 5,1 \leq v_i \leq 10^9)$.
Next line contains one integer the number of queries Q and each of the following Q lines contains two integers $s_i$ and $t_i (1 \leq s_i \leq n, 1 \leq t_i \leq 10^5)$ 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 $10^4$, and no more than 10 test cases that n is greater than $10^3$. sum of all Q are not greater than $2 \times 10^5$.
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 $subtree_s$ with total volume t.
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
Case #i:
15
2
3
Case #2:
4555
12
-1
The tree in first case looks like the picture above,
For query subtree_s =1,t= 15,we should pick items in subtree 1. only method is to pick all
items in subtree 1 and get value 15.