Call a Meeting

Alice and Bob are hosting a programming contest in Abiland. All the judges live in different cities (or same). On the contest day, all judges are going to be present at contest venue. Alice and Bob will pay the travel cost of all the judges. They want to minimize total traveling cost. Cities are connected by roads like a tree. Judges can move alone or can form a group with other judges. Cost of the traveling between cities depends on the size of the group. Two groups can merge. After merging, all members of previous two group will be in the new group. If two judges are in the same group at some point then they will be in same group forever.

The government of Abiland offers Alice and Bob and all contestants x free tickets per person. Using those tickets Alice and Bob can relocate contest venue. However, these tickets can’t be used for the transportation of the judges.

Now, you are given the number of cities $n$ (cities are numbered from 1 to $n$), the number of judges $m$ and their current cities, all the roads that connect two cities. You have to tell the minimum cost of traveling for all judges to the contest venue. All contestants, Alice and Bob and Contest Venue are now in city 1. By moving all contestants, Alice and Bob can relocate the contest venue. To pass a road contestants, Alice and Bob use 1 ticket each and they cannot pass a road if they have no tickets left.

Input

Input starts with an integer $T$ ($0 < T \le 70$), denoting the number of test cases. Each case starts with an integer $n$ ($1 \le n \le 100000$), followed by $m$ ($1 \le m \le 6$) and $x$ ($0 \le x \le 1000$).

The next line contains $m$ space separated integers between 0 and $10^9$, the $i$-th integer in this line denotes the cost of passing a road if a group of size $i$ travels.

The next line contains $m$ space separated integers between 1 and $n$, denoting the current city of the judges respectively.

Then there are $n - 1$ lines each containing two integers, $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) meaning that there is a road between city $u$ and $v$.

The sum of n in one file is $≤ 100000$.

Output

For each case, print the minimum traveling cost that Alice and Bob must pay so that all the judges can reach the Contest Venue.

Sample

Input	Output
2 5 1 5 2 4 1 2 1 3 2 4 2 5 5 3 0 2 1 1 4 5 3 1 2 1 3 2 4 2 5	0 7