Best Non-Adjacent Nodes

Statement

You are given a tree with n nodes numbered 1 to n. Node i has a weight. Choose a set of nodes so that no two chosen nodes are connected by an edge, maximising the total weight of the chosen nodes.

Input

The first line has n. The second line has the n weights. Each of the next n - 1 lines has two nodes joined by an edge.

Output

Print one integer: the maximum total weight.

Constraints

1 <= n <= 200000
1 <= weight <= 10^9
The edges form a tree.
The answer is at most 2 * 10^14.

Example 1

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

16

Choose nodes 2, 3 and 7: 4 + 5 + 7 = 16.

Example 2

1
5

5

A single node.