H. No Anime 2
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a tree with $$$n$$$ nodes rooted at node $$$1$$$; each node has a value $$$a_i$$$. Tortles and Keys both start at the root of the tree. Every second, Keys can choose to either move once to an adjacent node or choose to stay at the current node. On the other hand, Tortles can only move once every two seconds. Keys always makes his move before Tortles. Tortles is chasing Keys, and will always move towards Keys on the direct path between them. Keys' goal is to collect as much money as he can. After Keys either makes a move or chooses to stay, Keys will get $$$x$$$ dollars, where $$$x$$$ is the value of the node he is currently at. However, if Tortles ever is on the same node as Keys outside of their initial intersection at the root, Keys has to leave the tree and can no longer continue getting money. This also means that if Keys decides to make a move onto the same node Tortles is at, Keys has to instantly leave the tree and will not collect any money from that node.

If Keys must make a move away from the root in the first second, what is the maximum amount of money he can obtain?

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 4000$$$).

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

The next $$$n - 1$$$ lines contain two integers $$$u$$$ and $$$v$$$, denoting an edge from the $$$u$$$-th node to the $$$v$$$-th node ($$$1 \le u, v \le n, u \neq v$$$). It is guaranteed that the given edges form a valid tree.

Output

Output a single integer denoting the maximum amount of money Keys can obtain before he is inevitably caught. It can be shown that Tortles will always eventually catch Keys.

Examples
Input
5
1 2 3 4 5
1 2
2 3
3 4
3 5
Output
25
Input
10
1 1 1 1 1 1 1 1000 10 990
1 2
2 3
3 4
4 5
5 6
6 7
7 8
6 9
9 10
Output
8006
Note

In the first sample, an optimal route for Keys looks like the following: Move from node $$$1$$$ to node $$$2$$$ and then collect $$$2$$$ dollars. Then, move from node $$$2$$$ to node $$$3$$$ and collect $$$3$$$ dollars. At this point, Tortles will move from node $$$1$$$ to node $$$2$$$. Then, Keys should move to node $$$5$$$, and stay there for $$$4$$$ seconds to collect $$$4 \cdot 5 = 20$$$ dollars before Tortles eventually catches Keys.