Problem G
Caving

You recently took on the pastime of caving, primarily because of the treasures that are hidden behind the darkness. Whenever you head into a cave, you map out its structure and assign each cavern an integer value denoting your speculation of the worth of exploring that cavern. This value can be negative.

You recently heard about this newly discovered cave and cannot wait to explore it. You have already mapped it out and assigned each cavern a value. While mapping the cave out, you realized that the cave is fully connected, with $n$ caverns connected by $n - 1$ corridors.

The local government does not want its residents to miss out on the fun, so they are planning on clearing out the cave at the pace of one cavern per day starting tomorrow, so that the cave will be safe for the public to enter by the end of day $n$. The expedition team clears one of the caverns every morning, removing any treasures or dangers, effectively causing the value of that particular cavern to become $0$.

You usually go on caving adventures in the afternoon (after the government clears out a cavern), and the first expedition by the government is taking place tomorrow morning. Today is day $0$; you may go on a caving adventure today (before the government has cleared out any caverns), and you may go on caving adventures on any future day as well (even after the government has cleared all caverns). If you decide to go caving one afternoon, you can choose any of the $n$ caverns to drop down to, explore that cavern, and then you can choose to explore any other cavern connected to caverns you have explored by a corridor. The total value of such an adventure is the sum of the values of the caverns you explore, and you wonder what is the maximum possible value you can get out of an adventure. Since you also want to go caving as soon as possible, find the earliest day you can get the maximum possible value on.

Input

The first line consists of an integer $n$ ($1 \leq n \leq 100\, 000$), the number of caverns.

The second line consists of $n$ integers $v_1, \dots , v_ n$ ($-10^9 \leq v_ i \leq 10^9$), where $v_ i$ is the value of the $i$th cavern. The expedition team will clear out cavern $i$ on day $i$.

The next $n - 1$ lines consist of two integers $u$, $v$ ($1 \leq u, v \leq n$, $u \neq v$), denoting that there is a corridor between cavern $u$ and cavern $v$.

Output

Output the maximum value of a caving adventure and the earliest day you can achieve it on, separated by a single space. The starting day (today) is day $0$.

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

9 0

7
-4 -6 3 1 9 -8 0
5 4
5 6
4 1
6 7
6 3
1 2

10 0

7
-2 -4 -3 -4 -3 -5 -2
2 5
2 1
2 4
5 6
1 3
4 7

0 1