Maximum Harmony Score of the Life Tree

In the mystical X Forest, God created the Life Tree. Each node (including leaves) of the tree is assigned an integer representing its harmony value. God wants to select a set (S) of nodes (possibly empty) such that for any two nodes (a, b \in S), there exists a sequence of nodes ({a, v_1, v_2, \ldots, v_k, b}) where every node in the sequence is in (S) and every two consecutive nodes are directly connected by an edge. Under this connectivity condition, the goal is to maximize the sum of the harmony values of the nodes in (S). The maximum sum that can be achieved is the score given to the Life Tree.

Note: The empty set is allowed (with a sum of 0) in case selecting any nodes results in a negative sum.

inputFormat

The input consists of multiple lines:

The first line contains an integer (n) representing the number of nodes in the tree.
The second line contains (n) space-separated integers, where the (i)-th integer represents the harmony value of node (i).
Each of the next (n-1) lines contains two integers (u) and (v) (1-based indices) indicating that there is an edge connecting node (u) and node (v).

outputFormat

Output a single integer, which is the maximum possible sum of harmony values achievable by selecting a connected subset (S) of nodes (the empty set is allowed with a sum of 0).

sample

1
-5

0