校长要举办party了

题目描述

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

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

输入说明

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

输出说明

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

样例

输入

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

输出

5