J. Joyful City
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The president of Treetopia has built $$$n - 1$$$ bidirectional roads connecting the $$$n$$$ cities in the country, in such a way that it is possible to travel from any city to any other using the constructed roads.

To simplify traffic, the president decided to assign a direction to each road so that it is only possible to traverse it in that direction. Additionally, she determined $$$n$$$ values $$$b_0, b_1, \dots, b_{n - 1}$$$ such that the beauty of a city with exactly $$$k$$$ outgoing roads (that is, $$$k$$$ roads that are directed away from the city) is equal to $$$b_k$$$.

The president wants to assign the directions of each road in such a way that the sum of the beauties of all the cities is maximized. What is the maximum sum of beauties she can achieve?

Input

The first line of the input contains an integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of cities in Treetopia.

The next line contains $$$n - 1$$$ integers $$$b_0, b_1, \dots, b_{n - 1}$$$ ($$$1 \le b_i \le 10^9$$$), where $$$b_k$$$ represents the beauty of a city with exactly $$$k$$$ outgoing roads.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$), describing a road between cities $$$u$$$ to $$$v$$$. It is guaranteed that it is possible to go from any city to any other using these roads.

Output

Print a single integer — the maximum possible sum of beauties of all the cities after directing the roads.

Examples
Input
5
1 2 3 3 1
1 2
1 3
2 4
2 5
Output
9
Input
2
2 3
1 2
Output
5
Input
10
2 5 4 1 2 5 3 1 5 7
1 9
5 3
5 4
6 3
9 8
5 8
1 7
10 9
4 2
Output
47