Description

有一棵$n$个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？

Format

Input

第一行包含一个整数$n$。 接下来的一行包含$n$($n \leq 100000$)个正整数，第$i$个正整数( $\leq 1000$)代表点$i$的权值。 接下来一共$n-1$行，每行描述树上的一条边。

Output

输出一个整数，代表选出的点的权值和的最大值。

Samples

5
1  2  3  4  5
1  2
1  3 
2  4
2  5

12

Hints

样例说明 选择3、4、5号点，权值和为3+4+5=12。