問題文

茶碗蒸しくんときりくんはシュークリームが大好きなので、2人でシュークリームゲームをしようとしています。
シュークリームゲームは、木の上で行うゲームです。 木は $N$ 頂点、 $N-1$ 辺からなります。頂点には $1$ から $N$ の番号が付いていて、 $i\ (1\le i \le N-1)$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。 頂点 $i\ (1\le i\le N)$ にはシュークリームが $A_i$ 個置かれています。
茶碗蒸しくんから始めて、すべての頂点が選ばれるまで、交互に次の操作を行います。

• 既に選ばれた頂点と隣接するまだ選ばれていない頂点を1つ選ぶ（ただし、茶碗蒸しくんの最初のターンは頂点1を選ぶ）
• 選んだ頂点に置かれているシュークリームをすべて食べる

入力

$N$
$A_1\ A_2\ \cdots A_N$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_{N-1}\ v_{N-1}$

入力はすべて整数
$1\le N \le 1000$
$1\le A_i\le 10^9\ (1\le i\le N)$
$1\le u_i,\ v_i\le N\ (1\le i\le N-1)$
$u_i\neq v_i\ (1\le i\le N-1)$
与えられるグラフは木であることが保証される。

出力

答えを表す整数を1行に出力してください。
最後に改行してください。

サンプル

4
60 20 50 40
1 2
1 3
3 4

30

4
60 20 50 100
1 2
1 3
3 4

-10