Rockdu 教授对树问题很感兴趣，最近他创造了一种名为 Rock Tree 的新数据结构。

给定一个常数 $k$ 和一棵树 $T = \{V, E\}$，其中 $V$ 是节点集，$E$ 是边集。一个非空的节点集合 $A$ 被称为 $T$ 的 Rock Tree，当且仅当：

• $A \subseteq V$
• $A$ 中的所有节点在 $T$ 中是连通的，这意味着对于 $A$ 中的任意两个节点 $u$ 和 $v$，在 $T$ 中连接 $u$ 和 $v$ 的最短路径上的所有节点也都属于 $A$。
• $A$ 中任意两个节点之间的最大距离不超过 $k$。树中两个节点 $u$ 和 $v$ 之间的距离定义为它们在最短路径上的节点数（包含 $u$ 和 $v$）。

现在 Rockdu 构造了一棵有 $n$ 个节点的树 $R$，每个节点 $i$ 都被赋予了一个权值 $a_i$。他想要找到权值之和最大的 Rock Tree。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, k$ ($1 \le n \le 10^5, 1 \le k \le n$)，分别表示节点数和距离限制。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($|a_i| \le 10^4$)，表示节点的权值。

接下来的 $n - 1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示 $u$ 和 $v$ 之间的一条边。保证这些边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $10^6$，且 $n > 50000$ 的测试用例不超过 4 个。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最大权值和。

样例

输入 1

2
7 3
3 2 -2 -6 6 3 -7
1 2
2 3
2 4
2 5
5 6
2 7
12 5
0 7 -1 3 -3 10 -1 -1 -5 -1 -4 -9
1 2
1 3
1 4
2 5
4 6
6 7
1 8
8 9
5 10
9 11
9 12

输出 1

11
20