A. Note-takers
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Esomer doesn't want to go to class at university, but he needs notes from his lectures to be able to study. Therefore, he has come up with the following system.

The university can be represented as a tree of $$$n$$$ nodes, and on a single day, Esomer will have $$$k$$$ classes on consecutive hours. Additionally, Esomer will hire note-takers. A note-taker can be hired at node $$$i$$$ at any time for a cost of $$$c_i$$$. Additionally, all note-takers can move to any neighbor node of their current node between hours. Note that Esomer can hire several note-takers at the same node and at the same time, and at any point in time, several note-takers can be at the same node.

Esomer's demand is simple, for each of his $$$k$$$ classes at nodes $$$v_1, v_2, \ldots, v_k$$$, there needs to be at least one note-taker at node $$$v_i$$$ at hour $$$i$$$, so that Esomer will get the notes for the class.

Unfortunately, Esomer is not rich, so he wants to pay the least possible amount in total, and he has asked for your help in calculating that quantity.

Input

The first line contains a single integer $$$t$$$, the number of test cases $$$(1 \le t \le 50)$$$.

The first line of each test case consists of two integers $$$n$$$ and $$$k$$$, the number of nodes of the tree and the number of classes Esomer has to attend, respectively $$$(1 \le n \le 10^5, 1 \le k \le 200)$$$.

The second line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$, where $$$c_i$$$ denotes the cost of hiring a note-taker at node $$$i$$$ $$$(1 \le c_i \le 10^9)$$$.

Then follow $$$n-1$$$ lines, each with a pair of integers $$$a_i, b_i$$$, describing the edges of the tree $$$(1 \le a_i, b_i \le n, a_i \neq b_i)$$$.

Each test case ends with a line with $$$k$$$ integers, $$$v_1, v_2, \ldots, v_k$$$, such that Esomer needs to have a note-taker at $$$v_i$$$ at hour $$$i$$$ for all $$$1 \le i \le k$$$ $$$(1 \le v_i \le n)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases is at most $$$10^5$$$ and that the sum of $$$k$$$ over all test cases is at most $$$200$$$.

Output

For each test case, output a single integer equal to the minimum possible amount that Esomer must pay.

Example
Input
2
6 5
6 5 2 1 7 9
1 4
1 6
3 2
6 3
3 5
6 2 6 4 4
9 10
10 3 3 9 1 10 5 8 1
3 7
6 1
7 6
8 6
4 7
8 9
2 7
9 5
3 9 5 9 9 4 4 5 8 8
Output
12
5