#2675 Herding Sheep

4 s   128 MB  


Elly and her herd of sheep are in trouble again. After a long day of grazing it is time to bring them into the barns in order to be safe for the night. The size of the barns is limited - each barn can accommodate at most K sheep. Some of the barns might not be entirely filled; they can even remain completely empty. It is only important that each sheep is in a barn.

For simplicity the sheep can be represented as N points and the barns as M points with integer coordinates on the plane. It is possible that several sheep, several barns or several sheep and barns share the same coordinates.

Elly’s sheep walk a unit of distance per second. Thus, if for example one of them is at position (0, 0) and wants to go to a barn at (1, 3) it will need approximately 3.16227766 seconds to arrive at its destination. If the barn was at coordinates (3, 4) instead, the animal would need exactly 5 seconds to get there.

Help Elly by calculating the minimal time needed for all sheep to get into barns. The sheep can move simultaneously and you can assume that they do not disturb each other’s movement.


The first line of the input consists of a single integer, T, the number of test cases.

Each test case begins with three integers, N, M, and K – the number of sheep, the number of barns, and the maximum number of sheep in a barn, respectively.

After that follows N lines, each with two integers, X and Y , giving the x and y coordinates of a sheep.

Finally comes M lines, each with two integers, X and Y , giving the x and y coordinates of a barn.


For each test case, output the minimum time needed to get all sheep into barns, such that there are at most K sheep in any given barn. The answer should have a maximum relative or absolute error of at most 10−6. (output must be expressed decimal 9 points.)

Sample Input

Sample Output

5 3 2
2 13
9 6
4 8
13 7
11 3
2 11
10 6
4 12
7 3 3
-959 -542
-669 -513
160 717
473 344
-51 -548
703 -869
270 -181
957 -509
-6 937
-175 434


IDI Open 2014 H