有个公司要举行一场晚会。由于公司的职员有不同的职务级别，可以构成一棵以老板为根的人事关系树。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司……都可以邀请。已知每个人最多有唯一的一个上司。公司的每个人参加晚会都能为晚会增添一些欢乐，求一个邀请方案，使欢乐值的和最大。

第1行一个整数N（1≤N≤6000）表示人数。
第2行N个整数。表示第i个人的欢乐值（－128≤欢乐值≤127）。
接下来每行两个整数L，K。表示第K个人是第L个人的上司。
输入以0 0结束。

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

5