Reimu's birthday is coming up, and to prepare a gift for her, Marisa excitedly went to the shopping street. The shopping street has $n$ stores, and the roads between them form a tree.
The $i$-th store only sells the $i$-th type of goods, Reimu's liking for this type of goods is $w_i$, the price of the goods is $c_i$, and the stock is $d_i$. However, the shopping street has a strange rule: if you buy goods at stores $u$ and $v$, and there is a store $p$ on the path from $u$ to $v$, then you must also buy goods at store $p$. Marisa has $m$ coins, she wants to make Reimu as happy as possible, so she wants to maximize the total liking of the goods purchased.
### Input
- The first line is a positive integer $T$, indicating the number of test cases.
- For each test case,
- The first line contains two positive integers $n$ and $m$.
- The second line contains $n$ non-negative integers $w_1, w_2, ..., w_n$.
- The third line contains $n$ positive integers $c_1, c_2, ..., c_n$.
- The fourth line contains $n$ positive integers $d_1, d_2, ..., d_n$.
- The next $n-1$ lines, each containing two positive integers $u$ and $v$, indicate there is a road between $u$ and $v$.
### Output
- Output $T$ lines, each line is an integer, indicating the maximum total liking.
### Constraint
- $1 \leq n \leq 500$
- $1 \leq m \leq 4000$
- $1 \leq T \leq 5$
- $0 \leq w_i \leq 4000$
- $1 \leq c_i \leq m$
- $1 \leq d_i \leq 100$
### Example
Input
```
1
3 2
1 2 3
1 1 1
1 2 1
1 2
1 3
```
Output
```
4
```
