Pharaoh Tomeses LXVII is a ruler who uses advanced engineering, constructing a triumphant network of canals stemming from the River Nile. Specifically, there are a number of junctions connected by canals carrying water all throughout Egypt, allowing easy drinking, hygiene, and farming.

However, due to droughts and blights Tomeses is forced to restrict water usage and thus decrees that each junction can only have one open outgoing canal. Additionally, each junction has a certain fertility value determined by the value of the farms fed by it. Given that the junctions and canals form a tree and Tomeses' decree must be implemented, what is the maximum total fertility that can be obtained in the Nile network?

Input

The first line contains a single integer ~n~ (~1 \leq n \leq 5\times 10^4~), the number of junctions. These junctions are labelled ~1~ to ~n~, with junction ~1~ representing the River Nile and being the root of the tree.

The next line contains ~n~ space-separated integers ~a_1\ \dots\ a_n~ (~1 \leq a_n \leq 10^9~), representing the fertility value of each junction.

The next ~n-1~ lines each contain two integers ~u\ v~ (~1 \leq u < v \leq n~). Each line represents a canal between the ~u~th and ~v~th junction (i.e. that ~u~ is ~v~s parent). These junctions and canals form a tree rooted at the River Nile.

Output

Assuming that water can only flow through one outgoing canal for each connected node, starting at the root ~1~, what is the maximum total fertility score that Tomeses can obtain to fend off starvation for his people?

Hint

If you wish to use Python for this problem, you might need to try iterative approaches rather than recursive. You could alternatively try using Pypy3 for your submission.

Example

Input 1

5
1 2 3 4 1
1 2
1 3
3 4
3 5

Output 1

8

The junctions and canals are shown in the above image. The open canals in order to obtain the optimal ~8~ score are highlighted in red.

Input 2

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

Output 2

13