10702: 校长要举办party了

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

为了庆祝山东建筑大学建立100周年,校长决定开一个party进行庆祝,但是出现了一个问题,因为领导们都是分等级的,谁都不愿意和比自己高一级的领导去参加,并且每个人都有一个参加party的开心值。例如副校长不愿意跟校长共同参加,因为校长比他大一级,主任不愿意跟副校长同时参加,因为副校长比主任大一级,而主任和校长参加的话就没事。

校长要怎么发送请柬,才能使得此次参加party的人的开心值之和最高。

Input

多组测试样例,第一个数为n0<n<1000)代表有n个人。接下来n行每行一个数字ki(0<ki<100),代表第i个人参加此次party的开心值。接下来n-1行,每行包含两个数字ab,表示ba高一个等级。

Output

能够参加此次party的人的开心值之和。

Sample Input Copy

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

Sample Output Copy

5