## Cut the Tree

Anna loves graph theory! She has an -vertex tree, , where each vertex :

- Is indexed with a unique integer from to .
- Contains a data value, .

Anna observes that *cutting* any edge, , in results in the formation of two separate trees denoted by and . She also defines the following:

- The
*sum*of a tree is the sum of the values for all vertices in the tree. - The
*difference*between two trees created by cutting edge is denoted by .

Given the definition of tree , remove some edge such that the value of is minimal. Then print the value of the minimum possible as your answer.

**Note:** The tree is *always* rooted at vertex .

**Input Format**

The first line contains an integer, , denoting the number of vertices in the tree.

The second line contains space-separated integers where each integer denotes the value of .

Each of the subsequent lines contains two space-separated integers, and , describing edge in tree .

**Constraints**

- , where .

**Output Format**

A single line containing the minimum possible for tree .

**Sample Input**

```
6
100 200 100 500 100 600
1 2
2 3
2 5
4 5
5 6
```

**Sample Output**

```
400
```

**Explanation**

We can visualize the initial, uncut tree as:

There are edges we can cut:

- Edge results in
- Edge results in
- Edge results in
- Edge results in
- Edge results in

We then print the minimum of , , , , and as our answer, which is .