Given a tree which has ~n~ nodes, numbered from ~0~ to ~n-1~. Node ~0~ is the root of the tree. Each node has its weight which is an integer number. Write a program to calculate the weight of all subtrees, which is the total weight of all the subtree's nodes.

Input

• The first line contains the number of nodes ~n~ ~(1 ≤ n ≤ 10^5)~.
• The second line contains ~n~ integers which are the weight of node ~0~ to node ~n-1~ respectively.
• Each of the next ~n-1~ lines contains ~2~ integers ~u, v~ representing an edge between ~u~ and ~v~.

Output

• Print out the maximum weight of all subtrees.

Sample Input

6
1 5 0 2 -5 1
1 0
2 0
2 3
2 4
2 5

Sample Output

5