Ural大学有$N$个职员，编号为$1 \cdots N$。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

输入格式

第一行一个整数$N$。($1 \leq N \leq 6000$)

接下来$N$行，第$i+1$行表示$i$号职员的快乐指数$R_i$。($-128 \leq R_i \leq 127$)

接下来$N-1$行，每行输入一对整数$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

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$32768\mathrm{KB}$