题目描述

小 $A$ 开发了一款树上的游戏。

游戏界面上有一棵树，该树共有 $N$ 个结点，由 $N - 1$ 条边将树上所有的结点连在一起。

树上的第 $i$ 个点，有 $C_i$ 个金币，游戏人物只要移动到第 $i$ 个点，他可以选择拿走这个结点上的 $C_i$ 个金币，也可以选择不拿这个结点上的金币。

如果游戏人物选择拿走第 $i$ 个结点上的 $C_i$ 个金币，当游戏人物离开这个结点时，金币会重新产生。也就是说，游戏人物下次再走到第 $i$ 个点，任然可以选择拿走这个结点上的 $C_i$ 个金币。游戏人物每经过树上的一条边，就能获得 $1$ 个点的经验值。

游戏共有 $M$ 轮，每轮游戏开始，游戏人物会空降到树上编号为 $U_i$ 的结点，它的目标点是树上编号为 $V_i$ 的结点，当游戏人物到达目标点，本轮游戏结束。在每轮游戏中，游戏人物只能取走从 $U_i$ 出发到 $V_i$ 结束这条路线上的其中一个结点上的金币。

请你编程计算出，当 $M$ 轮游戏结束后，游戏人物最多可以获得多少金币、多少经验值。

输入格式

第 $1$ 行，读入 $2$ 个整数 $N, M$。

接下来的 $N - 1$ 行，每行读入 $2$ 个整数 $X_i, Y_i$，表示第 $i$ 条边连接编号为 $X_i$ 和编号为 $Y_i$ 的两个结点。

接下来的 $1$ 行，该行共有 $N$ 个整数，依次代表从编号为 $1, 2, 3, … , N - 2, N - 1, N$ 的结点，每个结点上的金币数量。

接下来的 $M$ 行，每行读入 $2$ 个整数 $U_i, V_i$，表示第 $i$ 轮游戏开始时，游戏人物空降到编号为 $U_i$ 的结点，目标点是编号为 $V_i$ 的结点。

输出格式

输出一行，共 $2$ 个整数，分别代表 $M$ 轮游戏结束后，总共获得的金币和经验值。

样例

输入

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

输出

36 4

输入

6 3
2 1
5 2
3 2
6 2
4 1
9 1 9 4 15 1
3 6
5 3
4 1

输出

33 5

输入

10 10
2 3
3 8
10 2
5 8
6 5
9 10
6 4
10 7
3 1
14 4 16 3 18 5 6 3 5 16
3 4
8 6
5 7
3 8
6 2
10 9
6 7
3 7
6 2
4 9

输出

174 37

数据范围

对于 $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 100000$，$1 \le C_i \le 100000$，$1 \le X_i, Y_i \le N$，$X_i \neq Y_i$，$1 \le U_i, V_i \le N$，$U_i \neq V_i$。