某個遊戲中有 n 個城鎮以 1~n 編號，這些城鎮以 n-1 條道路連接，每條道路都是雙向通行且連接兩個不同的城鎮，已知從任兩個城鎮之間都可以經由這些道路通達。現在你要佔領一些城鎮來獲取最大的利益，佔領編號 i 的城鎮可以獲得 w[i]的利益，但是你佔領的城鎮必須內部可以互相通達，也就是說，若 i 與 j 都是你的領地，則從 i 出發可以只經過你自己的城鎮到達 j。請計算你最多可以獲得多少總和利益。

輸入格式

第一行是正整數 n，n>1，村莊以 1~n 編號。第二行有 n 個整數，依序是 w[1],w[2],…,w[n]。接下來有 n-1 行是道路的資料，每一行有兩個正整數 u 與 v， 代表有一條道路連接 u 與 v。n 不超過 1e5，每個城鎮利益的絕對值不超過 1e4。

輸出格式

最多可以獲得的總和利益。

範例輸入 1

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

範例輸出 1

3

範例輸入 2

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

範例輸出 2

7