你最近迷上了洞穴探险，主要是因为隐藏在黑暗背后的宝藏。每当你进入一个洞穴，你都会绘制出它的结构，并为每个洞室分配一个整数值，表示你对探索该洞室价值的估计。这个值可以是负数。

你最近听说了一个新发现的洞穴，迫不及待地想要去探索它。你已经绘制了它的地图并为每个洞室分配了价值。在绘制地图时，你发现这个洞穴是完全连通的，由 $n$ 个洞室和 $n - 1$ 条通道连接而成。

当地政府不想让居民错过这个乐趣，因此他们计划从明天开始，以每天清理一个洞室的速度清理洞穴，以便在第 $n$ 天结束时，洞穴可以安全地对公众开放。探险队每天早上会清理其中一个洞室，清除其中的任何宝藏或危险，这实际上会使该特定洞室的价值变为 $0$。

你通常在下午（在政府清理完一个洞室之后）进行洞穴探险，而政府的第一次清理工作将在明天早上进行。今天是第 $0$ 天；你可以在今天进行洞穴探险（在政府清理任何洞室之前），你也可以在未来的任何一天进行洞穴探险（甚至在政府清理完所有洞室之后）。如果你决定在某个下午去探险，你可以选择 $n$ 个洞室中的任意一个作为起点降落，探索该洞室，然后你可以选择探索与你已探索的洞室通过通道相连的任何其他洞室。这样一次探险的总价值是你所探索的洞室价值之和，你想知道一次探险所能获得的最高可能价值是多少。由于你也想尽早去探险，请找出你能获得该最大可能价值的最早一天。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示洞室的数量。

第二行包含 $n$ 个整数 $v_1, \dots, v_n$ ($-10^9 \le v_i \le 10^9$)，其中 $v_i$ 是第 $i$ 个洞室的价值。探险队将在第 $i$ 天清理第 $i$ 个洞室。

接下来的 $n - 1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \ne v$)，表示洞室 $u$ 和洞室 $v$ 之间有一条通道。

输出格式

输出一次洞穴探险的最大价值以及你能获得该价值的最早一天，两者之间用一个空格分隔。起始天（今天）为第 $0$ 天。

样例

输入样例 1

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

输出样例 1

9 0

输入样例 2

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

输出样例 2

10 0

输入样例 3

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

输出样例 3

0 1