Currently you are present at Downtown Rockport arena. You have got one of the best cars of the world Lamborghini Aventador. The Rockport area consists of n checkpoints and m roads connecting the checkpoints.
The ith road connects two different checkpoints, Ai and Bi, and it requires Pi litres of petrol to drive along and can be traversed in either direction. There may be multiple roads running directly between any given pair of checkpoints.
You have k friends whom you have to pick from a certain checkpoint and drop at another checkpoint.
But your friends have a condition which you have to follow, because if you don't, they will not trust you anymore. The condition is you have to pick and drop your friends strictly in order, i.e. if i < j (1 <= i < j <= k), then the ith friend should be picked before the jth friend and the ith friend should also be dropped before the jth friend.
Note: You can carry at most q persons at a time in your car (excluding yourself). You have to start from position 1.
Since you have spent all your earnings in buying your dream car Lamborghini Aventador, you are short of money to buy petrol. The cost of petrol is given as Rs. 1 per litre of petrol (such a crazy place !!!).
Find the minimum cost to complete the above task.
Input:
The first line of input contains t - the number of test cases. Each test case goes as follows:
The first line contains 4 space-separated integers - n,m,k,q.
Each of the next m lines contain 3 space-separated integers - Ai,Bi,Pi.
Each of the next k lines contain 2 space-separated integers - Si,Di, i.e. the source and destination checkpoints of the ith friend.
Output:
Print t lines, each line containing the answer to the problem, or "-1" (without quotes) if the above task cannot be completed.
Constraints:
1 <= t <= 100
2 <= n <= 100
1 <= m <= 5000
1 <= k <= 5000
1 <= q <= 100
1 <= Ai, Bi <= n, Ai != Bi
1 <= Si, Di <= n, Si != Di
1 <= Pi <= 1000
Subtask 1: 30 points
1 <= q <= 2
Rest original constraints.
Subtask 2: 70 points
1 <= k <= 500
Rest original constraints.
Problem Setter:
Devesh Jagwani
Problem Tester:
Shikhar Kunal
3 8 10 4 4 1 2 1 1 3 1 2 3 1 2 4 1 2 6 1 5 6 1 3 5 1 3 7 1 5 8 1 4 8 1 2 8 3 4 5 4 6 4 7 9 4 3 1 2 1 1 3 1 2 3 1 2 4 1 2 6 1 5 6 1 3 5 1 3 7 1 5 4 1 2 4 3 4 5 4 6 4 7 8 4 2 1 2 1 1 3 1 2 3 1 2 4 1 2 6 1 5 6 1 3 5 1 3 7 1 2 3 3 5 5 4 6 4
