5932：Backpack on Tree

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.