Tracy needs to buy some cake! She finds herself at bakery ~1~ out of ~N~ total bakeries. Each bakery has it's own rating, some being so bad the rating is negative. Tracy can travel between two bakeries as long as there is a road connecting the two, and she will always stop at a bakery if she travels to it. It is also guaranteed that Tracy can travel to any bakery from bakery ~1~, but she can only visit each bakery once. She can also buy as many cakes as she wants, and she would like the sum of ratings for all bakeries she buys a cake from to be as high as possible. If she stops at a bakery, she must buy a cake there.

Input Specification

The first line will contain one integer ~N (1 \leq N \leq 10^5)~, the number of bakeries.

The next line will contain ~N~ space-separated integers, ~a_1, a_2, \ldots, a_n~, ~a_i (-10^5 \leq a_i \leq 10^5)~ representing the rating of the ~i~-th bakery.

The following ~N-1~ lines will contain two space-separated integers ~M~ and ~K (1 \leq M, K \leq N)~, indicating that there is an road between bakeries ~M~ and ~K~.

Output Specification

Output a single integer, the maximum possible sum of ratings.

Sample Input 1

3
0 10 15
1 2
1 3

Sample Output 1

15

Sample Input 2

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

Sample Output 2

3