【问题描述】

乌拉尔大学的校长打算举行建校80周年的晚会。大学的职员是分等级的，也就是说，职员之间的上下级关系组成了一棵以校长为根的树。职员用1到N之间的整数编号，人事处给出了每个职员的搞笑指数。为了使晚会的每个参加者都高兴，校长不会同时邀请一个职员和他的顶头上司．

你的任务是给出一个客人的列表，使得客人的搞笑指数之和最大。

【输入格式】party.in

第一行是一个整数N(1<＝N<＝6000)。

下面的N行每行是相应职员的搞笑指数。这个数的范围是－128到127。下面是职员的关系树。每行的格式是：L K,意思是第K个职员是第L个职员的顶头上司。输入以0 0结束。

输出格式party.out

最大的搞笑指数之和。

【样例输入】

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

【样例输出】

5