题目描述

某公司有 $n$ 名员工，编号为 $1\ldots n$。

他们之间有上下级关系，整体形成一棵以总经理为根的树，父结点是子结点的直接上级。

公司即将举办年会舞会，邀请每位员工参加都会带来一定的愉悦值 $r_i$，但如果某员工的直接上级也参加了，该员工就拒绝出席。

请计算邀请哪些员工可以使总愉悦值最大，输出最大愉悦值。

输入格式

第一行一个整数 $n$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i+1)$ 行的整数表示编号 $i$ 的员工的愉悦值 $r_i$。

第 $(n + 2)$ 到第 $2n$ 行，每行两个整数 $l, k$，表示 $k$ 是 $l$ 的直接上级。

输出格式

输出一行一个整数，表示最大的愉悦值。

样例

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

5

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\leq n \leq 6 \times 10^3$，$-128 \leq r_i\leq 127$，$1 \leq l, k \leq n$，且给出的关系一定是一棵树。