There are $N$ cities in a country, numbered $1$ through $N$. They are connected with $N-1$ undirected roads in such a way that one can move from one city to any other city through these roads. Each city contains a box filled with coins. The $i^{th}$ city contains a box with $A_i$ coins, and it requires $B_i$ consecutive seconds to open the box. 

Alice is initially in city $1$. While standing in city $i\;(1 \le i \le N)$, Alice can either:

• move to an adjacent city in $1$ second, or
• spend $B_i$ consecutive seconds to open the box in the  $i^{th}$ city and collect $A_i$ coins.

Find the maximum number of coins Alice can collect in $K$ seconds.

Alice can visit a city any number of times but can collect the coins only once from a city.

  Input format

• The first line of input contains two integers $N$ denoting the number of cities and $K$ denoting total seconds available to collect the coins.
• The second line contains $N$ integers $A_1, A_2,\dots, A_N$, denoting the number of coins in the cities.

• The third line contains $N$ integers $B_1,B_2,\dots,B_N$, denoting the number of seconds to open the boxes.

• $N-1$ lines follow. The $i^{th}$ line contains two integers $X_i, Y_i$ denoting a road between the cities $X_i,Y_i$. It is guaranteed that the roads and cities form a tree structure.

Output format
For each query, print the maximum number of coins Alice can collect in $K$ seconds.

Constraints

$1 \leq N, K \leq 300\\ 1\le A_i\le 10^5\\ 1 \le B_i \le 300\\ 1 \le X_i,Y_i\le N\\X_i \neq Y_i$