Description

Xiaomiao’s birthday is coming soon. To prepare a gift for Xiaomiao, Xiaocong excitedly came to the shopping street. There are $n$ shops on the street, and the roads between them form a tree.

Shop $i$ sells only item type $i$. Xiaomiao’s preference value for this item is $w_i$, the price is $c_i$, and the stock is $d_i$. However, the shopping street has a strange rule: if you buy things at shops $u$ and $v$, and there is a shop $p$ on the path from $u$ to $v$, then you must also buy something at shop $p$. Xiaocong has $m$ yuan. He wants to make Xiaomiao as happy as possible, so he wants to maximize the sum of preference values of the items he buys.

This small problem is of course easy for Xiaocong, but he has no computer with him. So he called you, a fellow OI contestant. Can you help him?

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case:

The first line contains two positive integers $n, m$.

The second line contains $n$ non-negative integers $w_1, w_2 \ldots w_n$.

The third line contains $n$ positive integers $c_1, c_2 \ldots c_n$.

The fourth line contains $n$ positive integers $d_1, d_2 \ldots d_n$.

The next $n - 1$ lines each contain two positive integers $u, v$, indicating that there is a road between $u$ and $v$.

Output Format

Output $T$ lines in total. Each line contains one integer, the maximum possible sum of preference values.

1
3 2
1 2 3
1 1 1
1 2 1
1 2
1 3

4

Hint

Constraints

For all test points, it is guaranteed that $1 \le n \le 500$, $1 \le m \le 4000$, $1 \le T \le 5$, $0 \le w_i \le 4000$, $1 \le c_i \le m$, $1 \le d_i \le 2500$.

Notes

Source: BZOJ4182.

Translated by ChatGPT 5