Anniversary Party

Ural University has N staff members, numbered 1 to N.

Their relationship structure is like a tree rooted at the president. The parent node is the direct supervisor of the child node.

Each staff member has a happiness index H_i (1 ≤ i ≤ N).

Now an anniversary party is to be held. However, no staff member is willing to attend with their direct supervisor.

Under this condition, the organizers want to select a group of staff to attend so that the total happiness index of the attendees is maximized. Find this maximum value.

Input Format

First line: an integer N.

Next N lines: the i-th line gives the happiness index H_i of staff member i.

Next N-1 lines: each line contains two integers L, K, indicating that K is the direct supervisor of L. (Note: the second number is the parent of the first number).

Output Format

Output the maximum possible total happiness index.

Constraints

1 ≤ N ≤ 6000

-128 ≤ H_i ≤ 127

Sample Input

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

Sample Output

5