Statement : F. Dynamic Values And Maximum Sum

F. Dynamic Values And Maximum Sum

You are given a tree$^{\text{∗}}$ with $n$ vertices numbered from 1 to $n$, where each vertex $i$ has an initial value $a_i$. You perform $k$ operations. The total is $0$ initially. In each operation:

Choose a vertex $r$ and root the tree at $r$.
Add the current value of $r$ to the total and set the value of $r$ to $0$.
For each vertex $ u $ that is not a leaf$^{\text{†}}$, find the leaves in the subtree$^{\text{‡}}$ of $u$ that are at the maximum distance from $u$. Among them, select the one with the smallest index, denoted as the destination for $u$. Add the current value of $u$ to the destination and set the value of $u$ to $0$.

Find the maximum possible total.

$^{\text{∗}}$A tree is a connected graph without cycles.

$^{\text{†}}$A leaf is any vertex without children.

$^{\text{‡}}$A subtree of vertex $v$ is the subgraph of $v$, all its descendants, and all the edges between them.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10 ^ 4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the initial values of vertices.

Each of the following $n-1$ lines contains two integers $u$ and $v$, denoting an edge connecting vertex $u$ and $v$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10 ^ 5$.

Output

For each test case, output an integer — the maximum possible total.

Example

Input

7
5 4
19 20 39 81 2
1 2
1 3
2 4
2 5
5 3
12 21 39 8 21
1 2
1 3
3 4
2 5
5 2
129 216 32 83 221
1 2
1 3
3 4
4 5
5 3
15 15 15 15 15
1 2
1 3
1 4
1 5
1 1
1
2 1
1 1000000000
1 2
7 2
8 3 5 7 9 1 6
4 3
7 5
5 2
2 3
3 6
6 1

Output

Note

Note

In the first test case:

Choose vertex $1$ as the root. Add $a_1 = 19$ to the total and set $a_1 = 0$.

After rooting the tree at $1$, for every non-leaf vertex $u$, move its value to the leaf in its subtree that is farthest from $u$ (breaking ties by smallest index). Under this rooting:

The value of vertex $2$ is transferred to vertex $4$, so $a_2$ becomes $0$ and $a_4$ becomes $101$.
The values of vertices $3$, $4$, and $5$ remain at their respective positions according to the rule.

Choose vertex $3$ as the root. Add $a_3 = 39$ to the total and set $a_3 = 0$.

After redistribution under this rooting, the values of vertices $4$ and $5$ remain at their positions.

Choose vertex $4$ as the root. Add $a_4 = 101$ to the total and set $a_4 = 0$.

After redistribution, the value at vertex $5$ remains unchanged.

Choose vertex $5$ as the root. Add $a_5 = 2$ to the total and set $a_5 = 0$.

The total obtained is $19 + 39 + 101 + 2 = 161$.

In the sixth test case, choose vertex $2$ as the root. Add its value to the total, obtaining $1,000,000,000$.