背景

WZOI的CJH教练经常出去旅游（机房男们那叫一个羡慕啊~~~~~）。当然，CJH教练的旅游可不是观赏风景那么简单……

问题描述

CJH教练预选了N个城市，打算去这些城市逛逛，并且要拍出一定质量的照片，第i个城市所能拍出的照片质量为Ci。可是，由于眼光有限，CJH教练选出的一些城市并不能拍出多少精彩的照片，因此，Ci可能小于零。N个城市由一些公路连通，每个城市之间有且只有一条路径使其连通。而CJH教练走的路线比较奇特，在他去的几个城市中，连通任意两个城市的路径上的城市，CJH教练也都要去过才行（其实就是要求经过的城市连通）。要知道，拍出的照片可是要在机房中展览的，CJH教练可不想让机房男嘲笑自己的拍照水准。鉴于机房男的审美观都不咋的，在好照片中混一些烂照片也不是不可以。CJH教练有些犯难，选哪些城市才能让照片总质量最高呢？

CJH教练非常看好你，就把这个光荣而艰巨的任务交给你了！

输入格式photo.in

输入数据第1行有1个正整数N，表示城市个数。

第2行有N个整数，第i个表示在第i个城市所能拍出的照片质量Ci。

接下来N – 1行，每行有两个整数u，v（1≤u,v≤N，u≠v），表示城市u与城市v之间有一条公路连接。

输出格式photo.out

输出数据仅一行，要求输出照片的最高总质量。

样例输入输出

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

4

4
-1 3 1 2
4 1
1 3
1 2

5

数据规模

对于10%的数据，N≤10，|Ci|≤1000；

对于30%的数据，N≤1000，|Ci|≤2000；

对于50%的数据，N≤10000，|Ci|≤4000；

对于100%的数据，N≤200000，|Ci|≤8000。