Ural大学将举行80周年校庆晚会。大学职员的主管关系像一棵以校长为根的树。为了让每一个人都玩的嗨皮，校长不希望职员和他的直接上司都在场。人事处已经评估了每个职员的欢乐度，你的任务是列出一个邀请职员名单，使参会职员的欢乐度总和最大。

职员的编号从1到N。

输入的第一行包含数字N(1≤N≤6000)。

后一行包含 N 个整数，表示每位职员的欢乐度。欢乐度是一个从-128到127整数。

之后的N-1行是描述主管关系树。每一行都具有以下格式:L K，表示第K名职员是第L名职员的直接主管。

输出参会职员欢乐度的最大和值。