题目描述

无向连通图 $\red{G }$ 有 $\red{n }$ 个点，$\red{n - 1 }$ 条边。点从 $\red{1 }$ 到 $\red{ n}$ 依次编号，编号为 $\red{i}$ 的点的权值为 $\red{W_i }$，每条边的长度均为 $\red{1}$。图上两点 $\red{(u, v)}$ 的距离定义为 $\red{ u }$ 点到 $\red{v}$ 点的最短距离。对于图 $\red{G }$ 上的点对 $\red{ (u, v)}$，若它们的距离为 $\red{2}$，则它们之间会产生$\red{W_v \times W_u}$ 的联合权值。

请问图 $\red{ G }$ 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

输入格式

第一行包含 $\red{1 }$ 个整数 $\red{n }$。

接下来 $\red{n - 1 }$行，每行包含 $\red{2 }$ 个用空格隔开的正整数 $\red{u, v}$，表示编号为 $\red{u }$ 和编号为 $\red{ v }$ 的点之间有边相连。

最后 $\red{1}$ 行，包含 $\red{n }$ 个正整数，每两个正整数之间用一个空格隔开，其中第 $\red{i}$ 个整数表示图 $\red{G}$ 上编号为 $\red{i}$ 的点的权值为 $\red{W_i}$。

输出格式

输出共 $\red{ 1}$ 行，包含 $\red{2}$ 个整数，之间用一个空格隔开，依次为图 $\red{ G }$ 上联合权值的最大值和所有联合权值之和。

由于所有联合权值之和可能很大，输出它时要对 $\red{10007 }$ 取余。

样例

样例输入

5
1 2
2 3
3 4
4 5
1 5 2 3 10

样例输出

20 74

样例说明

本例输入的图如上所示，距离为 $\red{2}$ 的有序点对有$\red{(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)}$。

其联合权值分别为$\red{2、15、2、20、15、20}$。其中最大的是 $\red{20}$，总和为$\red{74}$。

数据范围与提示

对于 $\red{30\% }$ 的数据，$\red{ 1 < n \leq 100 }$；

对于 $\red{ 60\% }$ 的数据，$\red{ 1 < n \leq 2000}$；

对于 $\red{100\%}$ 的数据，$\red{1 < n \leq 200000, 0 < W_i \leq 10000}$。

保证一定存在可产生联合权值的有序点对。