Juan is playing a strategy war game called "Execution". The game is played in a tree having $$$N$$$ nodes, numbered with integers from $$$1$$$ to $$$N$$$.
Node $$$1$$$ is an indestructible bunker. When the game starts, each node other than the bunker contains a certain number of soldiers.
The game proceeds in turns. At the beginning of each turn, Juan must choose whether to attack a node or not. The bunker cannot be attacked. If Juan attacks a node, then he defeats every soldier in that node, and the game ends immediately on that turn. On the contrary, if Juan chooses not to attack, soldiers in each node other than the bunker move to a neighboring node, in the direction towards the bunker. The game then proceeds to the following turn.
Juan wants to defeat as many soldiers as possible. Moreover, he wants to defeat that maximum number of soldiers as soon as possible, that is, by playing the minimum number of turns.
The first line contains an integer $$$N$$$ ($$$2 \leq N \leq 2 \cdot 10^5$$$) indicating the number of nodes in the tree. Each node is identified with a distinct integer between $$$1$$$ and $$$N$$$.
The second line contains $$$N-1$$$ integers $$$T_2$$$,$$$T_3$$$,$$$\dots$$$,$$$T_N$$$ ($$$0 \leq T_i \leq 10^9$$$), indicating that when the game begins, node $$$i$$$ contains $$$T_i$$$ soldiers. It is guaranteed that when the game begins, there is at least one soldier outside of the indestructible bunker (node $$$1$$$), that is, $$$T_2 + T_3 + \cdots + T_N \geq 1$$$.
Each of the next $$$N-1$$$ lines contains two integers $$$U$$$ and $$$V$$$ ($$$1 \leq U, V \leq N$$$ and $$$U \neq V$$$), indicating that $$$U$$$ and $$$V$$$ are neighboring nodes in the game. It is guaranteed that these pairs of neighboring nodes define a tree.
A single line with two integers, indicating the maximum number of soldiers that Juan can defeat, and the minimum number of turns required to achieve it.
4 3 2 1 1 2 2 3 2 4
3 1
4 6 7 8 1 2 2 3 2 4
15 2
7 0 0 1 0 0 2 7 2 6 3 3 5 6 1 3 4 6 2
3 3
In the first sample, Juan could attack node $$$2$$$ on the first turn, defeating $$$3$$$ soldiers. If he didn't, on the second turn there would be $$$3$$$ soldiers in node $$$1$$$, $$$3$$$ in node $$$2$$$, and $$$0$$$ in the remaining nodes. At that moment, Juan could attack node $$$2$$$ and also defeat $$$3$$$ soldiers, but he would not achieve it in the minimum number of turns. Remember that attacking node $$$1$$$ is never allowed.
In the second sample, it is best for Juan to wait for a turn, and to attack node $$$2$$$ on the second turn.
