Xiao Ming wants to catch starfish on the seabed, which has a tree-like structure where starfish are hidden.

Given a tree with $n$ nodes, labeled $1, 2, 3, \dots, n$, with corresponding node weights $p_i$.

A starfish is defined as a flower subgraph within the tree. Let its center node be $O$ and its edge nodes be $a_1, a_2, \dots, a_t$ (where each edge node must be directly connected to the center node, and the flower subgraph must consist of at least one center node and one edge node). The value of such a starfish is defined as $|p_O - \sum p_{a_i}|$.

Xiao Ming wants to know the maximum total value of starfish he can catch. (He can catch multiple starfish at the same time, but the intersection of the sets of nodes of any two starfish must be empty.)

Supplementary definition: Flower graph: A connected graph with a diameter of at most 3, where the node with the maximum degree is the center node, and the remaining nodes are edge nodes (it can be seen that any edge node has a degree of 1). Example: The smallest flower graph is $(G,V)=(\{1,2\},\{(1,2)\})$, consisting of only two nodes and the edge connecting them.

Input

The first line contains a positive integer $n$, representing the size of the tree. The second line contains $n$ integers, representing $p_i$. The next $n-1$ lines each contain two integers $a, b$, representing an edge between node $a$ and node $b$.

Output

A single integer representing the maximum total value of starfish Xiao Ming can catch.

Examples

Input 1

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

Output 1

10

Note

A valid strategy is for Xiao Ming to catch two starfish. The first starfish has center node 1 and edge node 3, with a value of 6; the second starfish has center node 2 and edge node 5, with a value of 4. This yields a maximum total value of 10.

Constraints

(1) For 10% of the data, the structure is guaranteed to be a flower graph. (2) For 20% of the data, the structure is guaranteed to be a chain. (3) For 20% of the data, the product of weights of adjacent nodes is guaranteed to be always negative. (4) For 20% of the data, the structure is guaranteed to be a binary tree rooted at 1. (5) For 30% of the data, there are no special restrictions.

For all data, $1 \le a, b \le n \le 10^5$, $-10^9 \le p_i \le 10^8$. The provided sample data numbered $i$ and $i+5$ correspond to the constraint condition $i$, where $i \in \{1, 2, 3, 4, 5\}$.