GASWARS - Gas Wars

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 ci 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

Added by:Spooky
Date:2009-07-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Advancement Spring 2009, http://sevolymp.uuuq.com/

hide comments
2016-10-29 19:31:08
really easy
2015-07-28 19:36:04
i am confused in which algo used to solve this problem ?
2015-07-13 15:59:28 Rishav Goyal
nice problem :D
2014-03-14 15:12:52 Cosmin Rusu
Why do I get WA WA WA... I use binary search to search the answer... I found on the net a 100 points solution and it's the same as mine. Please help!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.