Little A and Little B are playing a game.

They are presented with a forest of rooted trees, where each node $u$ has a positive integer weight $A_u$.

Little A and Little B take turns, with Little A going first. The current player must choose exactly one tree root to remove, gaining its weight. The subtrees of the removed node become new rooted trees, and its children become the new roots.

The game ends when all nodes have been removed. A player's score is the sum of the weights of the nodes they removed.

Both players aim to maximize their own scores and play optimally. Calculate the final score of Little A.

The initial state consists of exactly one tree with $n$ nodes, labeled from $1$ to $n$, with node $1$ as the root.

Input

The first line contains a positive integer $n$, representing the number of nodes.

The second line contains $n$ positive integers $A_1, A_2, \dots, A_n$, representing the weight of each node.

The next $n-1$ lines describe the initial state, each containing two positive integers $u, v$ representing an edge between $u$ and $v$ in the tree. It is guaranteed that the input forms a tree.

Output

Output a single integer representing the final score of Little A.

Examples

Input 1

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

Output 1

7

Input 2

See provided files.

Constraints

For all data, $1 \leq A_i \leq 10^9$.

• Special Property A: Let $p_i$ be the parent of $i$. Then for all $2 \leq i \leq n$, $A_i \leq A_{p_i}$.
• Special Property B: All $A_i$ are chosen uniformly at random from the integers in $[1, 10^9]$.