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:

1. Choose a vertex $r$ and root the tree at $r$.
2. Add the current value of $r$ to the total and set the value of $r$ to $0$.
3. 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.

Note

In the first test case:

1. 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.

2. 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.
3. 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.
4. 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$.