There are iron balls numbered to , and the weight of the th ball is . We use springs to connect them into a tree.

The ball numbered is the root of the tree. Now we grasp the root and hang the whole tree.

The initial length of each spring is . If the weight of the subtree it hangs is , its length will become .

At this time, PaiGuDragon come up with an evil idea. It plans to rearrange the sequence, that is, PaiGuDragon is going to generate an array which is a permutation of , and then the weight of the th ball will become

Considering all the arrangements, what is the maximum of maximum depth of the tree after hanging?

Here, the maximum depth is defined as the maximum value of the sum of the spring lengths on the path from the leaf to the root.

The first line contains an integer .

The second line contains  integers  - the initial state of weight.

Each of the next  lines contains 2 integers  - an edge between .

It's guaranteed that the given graph is a tree.

Output an integer. maximum of maximum depth of the tree.

4
1 2 3 4
1 2
2 3
3 4

23

In the test case, keep original arrangement is a good idea.

maximum depth = (1+4) + (1+4+3) + (1+4+3+2) = 23