Problem Statement

There is a country with a tree structure, and the $N$ cities that make up the country are numbered $1, 2, \dots , N$.
The cities are connected by bidirectional highways, and the $i$-th highway connects city $A_i$ and city $B_i$.

This country has $K$ temples; the $i$-th temple is located in city $C_i$ and its value is $D_i$.

The god worshipped by this country is more pleased the larger the value $X$ defined by the following procedure is.

• Let $S$ be the sum of the values of the temples.
• Viewing the country as a tree rooted at city $1$, let city $T$ be the LCA of all cities that have a temple.
• $X$ is $S$ $+$ (the minimum number of roads that must be traversed on the way from city $T$ to city $1$).
• However, if no temples exist, $X$ is $-10^{10^{10}}$.

• Choose integers $l$ , $r$ ($1$ $\leq$ $l$ $\leq$ $r$ $\leq$ $K$) and annihilate with a beam all temples whose number (note that this is not the city number) is between $l$ and $r$, inclusive.
  

Input

$N\ K$
$C_1\ C_2\ \dots\ C_K$
$D_1\ D_2\ \dots\ D_K$
$A_1\ B_1$
$A_2\ B_2$
$\dots$
$A_{N-1}\ B_{N-1}$

• $2\leq K\leq N\leq 10^5$
• $1\leq C_i\leq N (1\leq i\leq K)$
• $C_i\neq C_j (1\leq i < j\leq K)$
• $-10^9\leq D_i\leq 10^9 (1\leq i\leq K)$
• $1\leq A_i,B_i\leq N (1\leq i\leq N-1)$
• All inputs are integers.
• The graph given in the input is a tree.

Output

Find the median of $X$. Print a newline at the end.

Sample

3 2
2 3
1 1
1 2
2 3

2

7 3
4 5 7
1 10 100
1 2
2 3
3 4
3 5
1 6
6 7

101