题目描述

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

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

格式

输入格式

第一行是一个整数 \(N\)。

接下来的 \(N\) 行每行是相应职员的搞笑指数。这个数的范围是\(-128\)到\(127\)。

下面是职员的关系树，每行的格式是：\(L\) \(K\)，意思是第 \(K\) 个职员是第 \(L\) 个职员的顶头上司，输入以\(0\) \(0\)结束。

输出格式

输出一行，包含一个整数，表示最大的搞笑指数之和。

样例1

样例输入1

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

样例输出1

5

限制

\(100\%\)数据：\(1 \le N \le 6000\)。