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 \)