A tree, , has vertices numbered from to and is rooted at vertex . Each vertex has an integer weight, , associated with it, and 's total weight is the sum of the weights of its nodes. A single remove operation removes the subtree rooted at some arbitrary vertex from tree .
Given , perform up to remove operations so that the total weight of the remaining vertices in is maximal. Then print 's maximal total weight on a new line.
Note: If 's total weight is already maximal, you may opt to remove nodes.
Input Format
The first line contains two space-separated integers, and , respectively.
The second line contains space-separated integers describing the respective weights for each node in the tree, where the integer is the weight of the vertex.
Each of the subsequent lines contains a pair of space-separated integers, and , describing an edge connecting vertex to vertex .
Constraints
Output Format
Print a single integer denoting the largest total weight of 's remaining vertices.
Sample Input
5 2
1 1 -1 -1 -1
1 2
2 3
4 1
4 5
Sample Output
2
Explanation
We perform remove operations:
- Remove the subtree rooted at node . Losing this subtree's weight increases the tree's total weight by .
- Remove the subtree rooted at node . Losing this subtree's weight increases the tree's total weight by .
The sum of our remaining positively-weighted nodes is , so we print on a new line.
