Mirko is tired of his stressful CEO job in a well-known multinational software company. With a golden parachute of several million dollars, he decided to live a simple life and move to Gorski Kotar. However, winters in the remote village he just moved in are tough. None of his neighbours were born after WWII, so he is destined to chop firewood himself.

Today, he is going to chop his first trunk. Before chopping, he labels the parts of the trunk which are small enough to fit in a fireplace, and measures their hardness.

Mirko is a programmer, so he notices that the parts and the connections between them form a tree graph.

The damage on his axe resulting from cutting a connection on the trunk is equal to the sum of the maximal hardnesses in the two connected components formed by cutting the connection.

Mirko has only one axe, so he wants the total damage to be as small as possible. He wants to know the minimal total damage on the axe, if he cuts the whole trunk into single parts which fit in a fireplace.

Input

The first line contains an integer ~n~, the number of parts. The parts are labeled by integers from ~1~ to ~n~.

The second line contains ~n~ integers ~t_i~ ~(1 \le t_i \le 10^9)~. The number ~t_i~ is the hardness of the part labeled ~i~.

Each of the following ~n-1~ lines contains two integers ~x~ and ~y~ ~(1 \le x, y \le n)~ – labels of parts that are directly connected.

Output

Output the minimal total damage after ~n-1~ cuts.

Scoring

In all subtasks it holds that ~1 \le n \le 100\,000~.

Subtask	Score	Constraints
~1~	~10~	~1 \le n \le 10~
~2~	~10~	Parts ~i~ and ~i+1~ ~(1 \le i \le n-1)~ are directly connected.
~3~	~30~	~1 \le n \le 1\,000~
~4~	~60~	~1 \le n \le 100\,000~

Sample Input 1

3
1 2 3
1 2
2 3

Sample Output 1

8

Explanation for Sample Output 1

There are two ways to cut this trunk. He can first cut the connection ~(1, 2)~, which causes ~1 + 3 = 4~ damage, and then cut the connection ~(2, 3)~, which causes ~2 + 3 = 5~ damage. The total damage is ~9~ in this case.

Otherwise, he can first cut ~(2, 3)~, and then ~(1, 2)~. The total damage in that case ~(2 + 3) + (1 + 2) = 8~.

Sample Input 2

4
2 2 3 2
1 3
3 2
4 3

Sample Output 2

15

Sample Input 3

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

Sample Output 3

26