Oscar is worried that his farm could become taken over by aliens. He has installed a warning system in case aliens show up, so that all his cows and pigs can run for cover. His farm can be represented by multiple pens connected by muddy paths. For every two pens, there is exactly one path that connects them and no path is used multiple times.

Oscar can install speakerphone in various clearings, such that each muddy path will have one of it's two pens set up with a speakerphone. However, the speakerphone cost a lot of money, so Oscar would like to know the minimum amount of money required to set up enough speakerphone in pens so that each path has one of its two endpoints with a speakerphone.

Given the price for installing a speakerphone at each clearing, can you output the minimum price Oscar has to pay to set up a speakerphone at least one end of each path?

Input Specification

The first line of input will begin with a single positive integer ~N (1 \leq N \leq 10^5)~, representing the number of clearings.

The next line contains ~N~ positive integers ~a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^{12})~, representing the cost of building a speakerphone at each pen.

The next ~N - 1~ lines will contain two integers ~U_i~ and ~V_i (1 \leq U_i, V_i \leq N)~, representing a muddy path connecting pens ~U_i~ and ~V_i~.

Output Specification

Output a single integer for each test case, the minimum cost required to build at least one speakerphone at one of the ends of each path.

Subtasks

Subtask 1 [30%]

~1 \leq N \leq 20~

~1 \leq a_i \leq 10^5~.

Subtask 2 [70%]

No additional constraints.

Sample Input

4
1 2 3 5
1 4
2 4
4 3

Sample Output

5