HZNUOJ

年会

Tags:   dp
Time Limit:  1 s      Memory Limit:   128 MB
Submission:13     AC:10     Score:99.43

Description

背景
某大学校长准备开一次年会. 该校的员工具有等级结构, 即师生关系构成一棵树, 以校长为树根. 员工号是1到N之间的整数. 人事部门把所有员工按活跃度排序. 为了让年会使所有参加者都玩的高兴, 校长不想让任何一个员工和他/她的直接导师同时被邀请.

你的任务是列一张客人名单, 以使客人活跃度最大.

Input

第1行是一个整数N. 1 ≤ N ≤ 6000.
接着的N行包含相应员工的活跃度.活跃度是一个-128到127之间的整数.
其后是师生关系表. 每行有如下形式:
L K
表示第K个员工是第L个的直接导师.
输入以
0 0
结束.

Output

输出是客人最大总活跃度.

Samples

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