Description

The president of Ural State University is preparing for the university's 80th anniversary celebration. Since the staff members have different hierarchical positions, they form a personnel relationship tree with the president as the root. Each staff member has a unique integer ID, numbered from 1 to N, and each has a corresponding happiness value for attending the celebration. To ensure that every staff member is happy, the president has decided that no staff member and their direct supervisor will attend the celebration simultaneously.

Your task is to design a list of attendees that maximizes the total happiness.

Input Format

The first line contains an integer N;

The next N lines correspond to the happiness values of the N staff members, where the i-th line contains an integer representing the happiness value p_i of the i-th staff member;

Following this is the personnel relationship tree of the university. Each line is in the format L K, indicating that the K-th staff member is the direct supervisor of the L-th staff member. The input ends with 0 0.

Output Format

Output the maximum total happiness achievable by the attendees.

Sample 1

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

5

Data Range and Hints

For 100% of the data, 1 ≤ N ≤ 6000, -128 ≤ p_i ≤ 127.