Description

给你一颗 $n+1$ 个节点的树和一个序列 $a[1....n]$

你要自己选一个点开始放入集合 然后每次选一个还没有加入集合并且有邻居加入集合的点

假设这是第$i$次操作，就把这个点和他的邻居之间的边权设置为 $a_i$

你需要最大化这棵树的直径 输出这个最大的直径

Input Format

第一行一个整数 $n$

第二行 $n$ 个整数 $a[1...n]$

接下来 $n$ 行每行两个整数 $x$ 和 $y$ 表示树上的一条边

Output Format

输出一行一个整数 表示答案

Sample

input

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

output

16

Hint

对于所有数据 $n\leq150$ $a_i\leq10^9$

$subtask1(20pts)$:$n\leq8$

$subtask2(25pts)$:$n\leq15$

$subtask3(10pts)$:$n\leq15$,$u_i=i$,$v_i=i+1$

$subtask4(15pts)$:$n\leq15$,$u_i=1$

$subtask5(20pts)$:$n\leq80$

$subtask6(10pts)$:$n\leq150$