Where Is That Bustling Marketplace Now

— Unconnected Marketeers

The Underground Great Line Network is a grand transit system connecting all corners of Gensokyo. Momoyo noticed that the network's layout resembled a tree$$$^{\text{∗}}$$$ structure. She couldn't help but imagine the most effective way to dismantle that tree.

Given a tree with $$$n$$$ nodes where node $$$i$$$ has weight $$$a_i$$$, select a simple path of exactly $$$k$$$ edges and remove all edges on it. This splits the tree into $$$k+1$$$ connected components, each with weight equal to the sum of its nodes' weights. You need to maximize the minimum component weight, or output $$$-1$$$ if no simple path of exactly $$$k$$$ edges exists.

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

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-1$$$, $$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers, where the $$$i$$$-th integer represents $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$).

The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$, representing an edge of the tree.

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

Output

For each test case, output the maximum possible minimum component weight, or $$$-1$$$ if no such path exists.

Note

In the first test case, consider the path $$$3\to4$$$. Removing this path yields components of weights $$$6$$$ and $$$4$$$.

In the fourth test case, take the path $$$1\to2\to5$$$. Removing this path yields components of weights $$$7$$$, $$$6$$$, and $$$9$$$.

Momoyo and the Network

Examples