该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一棵包含 $n$ 个节点的树，节点编号为 $1$ 到 $n$，节点 $i$ 上有 $C_i$ 枚金币。

游戏共进行 $m$ 轮。第 $i$ 轮从节点 $U_i$ 出发，沿树上唯一的简单路径走到节点 $V_i$。本轮可以从这条路径上的任意一个节点获取一次该节点的全部金币，因此本轮最多获得路径上金币数的最大值。不同轮次互不影响，节点上的金币会恢复。每经过一条边还会获得 $1$ 点经验值。

请计算全部 $m$ 轮中最多能获得的金币总数，以及获得的经验值总数。

输入格式

第一行包含两个整数 $n,m$。

接下来 $n-1$ 行，每行包含两个整数 $x,y$，表示节点 $x$ 和节点 $y$ 之间有一条边。

下一行包含 $n$ 个整数 $C_1,C_2,\ldots,C_n$。

接下来 $m$ 行，每行包含两个整数 $U_i,V_i$，表示一轮游戏的起点和终点。

输出格式

输出两个整数，依次表示最多能获得的金币总数和经验值总数，中间用一个空格分隔。

样例

5 3
4 1
5 4
3 4
4 2
11 12 6 12 5
4 1
2 1
4 3

36 4

数据范围与提示

• 对于 $30\%$ 的数据，$1 \le n,m \le 100$，$1 \le C_i \le 100$
• 对于 $60\%$ 的数据，$1 \le n,m \le 1000$，$1 \le C_i \le 1000$
• 对于 $100\%$ 的数据，$1 \le n,m \le 10^5$，$1 \le C_i \le 10^5$
• 输入的边保证构成一棵树
• $1 \le U_i,V_i \le n$，$U_i \ne V_i$