As the result of the gas wars the following agreement was made. The transit of the gas was allowed under the following conditions. There are n transit nodes and m pipes connecting those nodes. There k nodes where the gas enters and l nodes where it should be moved. Each pipe has a carrying capacity of c_i cubic meters of gas per day. Gas can go through the pipes in either direction. It is needed to move g cubic meters of gas in total through the pipeline every day. The cost of the transit is defined as maxC*100 thousand dollars, where maxC – maximum of carrying capacities of the used in the transit pipes (even those which are not fully used). You are to find the minimum possible cost of transit for the given pipeline.

Input

The first line of the input file contains t – the amount of test cases. The description of each test case follows. The first line of each test case contains five integers separated by spaces – n, m, k, l, g. Then m lines containing three integers a, b, c follow. Each lines means that nodes with numbers a and b are connected by the pipe with the carrying capacity of c. Next line contains k integers – the numbers of nodes where the gas should enter the pipeline. The last line of the test case contains l integers – the numbers of nodes where the gas should be moved. The gas can enter the pipeline in any of the k entrance nodes and can be moved to any of the l exit nodes. The nodes are numbered from 1 to n.

Constraints

1 <= t <= 20
2 <= n <= 100
1 <= m <= n*(n-1)/2
1 <= k, l <= n/2
1 <= g, c <= 1000000

Output

For each test case output a single integer on a separate line – the minimum cost of transit in thousands of dollars. If the transit of the needed volume is impossible, then output -1.

Example

Input:
1
6 8 1 1 1
1 2 1
1 3 2
2 4 3
2 5 3
3 4 4
3 5 2
4 6 4
5 6 1
1
6

Output:
200