Herding Sheep

Elly and her herd of sheep are in trouble again. After a whole day of grazing the sheep have to go into the barns so that they are safe for the night. One barn holds at most $K$ sheep. A barn does not have to be full and may stay empty. All that matters is that every sheep ends up inside some barn.

To keep things simple, the sheep are $N$ points and the barns are $M$ points with integer coordinates on the plane. Several sheep may share the same coordinates, several barns may share the same coordinates, and a sheep and a barn may share the same coordinates.

A sheep walks one unit of distance per second. A sheep at $(0, 0)$ that walks to a barn at $(1, 3)$ needs about 3.16227766 seconds, and a barn at $(3, 4)$ takes exactly 5 seconds. All sheep move at the same time and never block each other.

Compute the minimum time needed for all sheep to be inside barns. In other words, minimize the largest walking time over all sheep.

The first line contains one 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 one barn.

The next $N$ lines each contain two integers $X$ and $Y$, the coordinates of a sheep.

The next $M$ lines each contain two integers $X$ and $Y$, the coordinates of a barn.

• $1 \le T \le 20$
• $1 \le N, M, K \le 200$
• $-1000 \le X, Y \le 1000$
• $N \le M \times K$

For each test case, print the square of the minimum time as an integer on its own line. All coordinates are integers, so the square of the minimum time is always an integer. If the minimum time is 5 seconds, print 25.