H. Favorite Treat
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is baking treats for her two corgis, Bob and Charlie!

For some strange reason, Alice has arranged the $$$N$$$ treats she has baked in a tree structure. Each of the $$$N$$$ treats has an associated tastiness, with the $$$i^\text{th}$$$ treat having tastiness $$$t_i$$$.

Bob and Charlie will now play a game as follows:

  • While there are still treats left, Bob will select two treats which are leaves of the tree.
  • Charlie will choose one of the treats to eat, and Bob will be left to eat the other.
  • As the treats are eaten, they, along with their incident edge, are deleted from the graph.

As corgis are known to be extremely clever dogs, Bob and Charlie are both master logicians acting in their own best interest, which is to eat treats with maximum total tastiness. Alice is now curious, just how much will the total tastiness of the treats Bob eats be? Can you help her figure it out?

Input

The first line of input will contain a single integer $$$N\ (2 \leq N \leq 20)$$$, denoting the number of treats Alice has baked. It is guaranteed that $$$N$$$ is even.

The next line will contain $$$N$$$ space-separated integers, $$$t_1, t_2, \dots, t_N\ (1 \leq t_i \leq 2 \cdot 10^9)$$$, denoting the tastiness of each treat.

The following $$$N - 1$$$ lines will each contain two space separated integers $$$u$$$ and $$$v\ (1 \leq u, v \leq N, u \neq v)$$$ indicating that there is an edge between the $$$u^\text{th}$$$ treat and the $$$v^\text{th}$$$ treat. It is guaranteed that these edges form a tree.

Output

Output a single integer denoting the total tastiness of the treats Bob eats, assuming that both he and Charlie act optimally.

Examples
Input
4
1 2 10 100
1 2
3 2
4 2
Output
11
Input
4
1 10 50 100
1 2
3 2
4 2
Output
51
Note

The first sample test case looks like the following:

Optimally, Bob will choose the treats with tastiness 10 and 100 and then the treats with tastiness 1 and 2. Charlie will choose the treats with tastiness 100 and 2, leaving Bob with the treats worth 10 and 1 tastiness, for a total of 11.

The second sample test case looks like the following:

Bob's strategy should now be to choose the treats with tastiness 1 and 10, and then the treats with tastiness 50 and 100. Charlie will choose the treats with tastiness 10 and 100, leaving Bob with the treats worth 1 and 50 tastiness, for a total of 51.