Chase

Tom the cat is chasing Jerry the mouse again. Jerry wants an advantage, so he runs into crowds of pigeons where Tom has a harder time following him. He has just arrived at the central park of Ljubljana. The park has $n$ statues, numbered $1$ to $n$, and $n-1$ passages that do not cross each other and connect the statues so that every statue can be reached from every other statue. Around statue $i$ there are $p_i$ pigeons.

Jerry has $v$ breadcrumbs in his pocket. If he drops a breadcrumb at the statue he is standing at, the pigeons of every statue that a passage connects directly to it immediately fly to this statue to eat the crumb. As a result the number of pigeons $p$ around this statue and around its neighbours changes.

Everything happens in this order. First Jerry arrives at statue $i$ and meets the $p_i$ pigeons that are there. Then he drops the breadcrumb. Then he leaves the statue. The pigeons of the neighbouring statues move to statue $i$ before Jerry arrives at the next statue, so they do not count toward the number of pigeons he meets.

Jerry may enter the park at any statue and run along passages, but he may never use the same passage twice, and he leaves the park wherever he wants. After Jerry exits the park, Tom enters and walks exactly the same route. By dropping at most $v$ breadcrumbs, Jerry wants to maximise the difference between the number of pigeons Tom meets on the route and the number of pigeons he meets himself. Only the pigeons that are at a statue right before Jerry arrives there count toward his own total.

The first line contains the number of statues $n$ and the number of breadcrumbs $v$. The second line contains $n$ integers $p_1$ to $p_n$, separated by spaces. Each of the next $n-1$ lines contains two integers $a_i$ and $b_i$, which mean that a passage connects statue $a_i$ and statue $b_i$.

Print one integer, the maximum difference between the number of pigeons Tom meets and the number of pigeons Jerry meets.

• $1 \le n \le 10^5$
• $0 \le v \le 100$
• $0 \le p_i \le 10^9$

In the first example one optimal route is the following. Jerry enters the park at statue 6 and meets 5 pigeons there. He drops a breadcrumb, so $p_6$ becomes 27 and $p_5 = p_7 = p_8 = p_9 = 0$. Next he runs to statue 7 and meets 0 pigeons. He drops the second breadcrumb, so $p_7$ becomes 41 and $p_2 = p_4 = p_6 = p_{10} = 0$. He exits the park. He met $5 + 0 = 5$ pigeons. Tom follows the same route and meets $p_6 + p_7 = 0 + 41 = 41$ pigeons. The difference is $41 - 5 = 36$.