题目描述

Ural 大学有 $N$ 个职员，编号为 $1\sim N$。

他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

你的任务是设计一份参加聚会者的名单，使总欢乐度最高。

输入格式

第 $1$ 行一个整数 $N$ 表示公司的人数。

接下来 $N$ 行每行一个整数。第 $i$ 行的数表示第 $i$ 号员工的快乐指数 $r_i$。

接下来每行两个整数 $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

数据范围

• 对于 $100\%$ 的数据，$1\le N \le 6000$， $-128 \le r_i \le 127$，$1 \leq l, k \leq n$，且给出的关系一定是一棵树。