양 몰기

엘리와 양 떼가 또 곤란한 상황에 빠졌다. 하루 종일 풀을 뜯었으니 이제 밤 동안 안전하도록 양을 우리에 넣어야 한다. 우리 하나에는 양이 최대 $K$마리까지 들어간다. 우리가 꽉 차지 않아도 되고 아예 비어 있어도 된다. 모든 양이 어느 우리 안에 들어가 있기만 하면 된다.

문제를 간단히 하려고 양은 평면 위 정수 좌표의 점 $N$개로, 우리는 점 $M$개로 나타낸다. 여러 양이 같은 좌표에 있을 수도 있고, 여러 우리가 같은 좌표에 있을 수도 있으며, 양과 우리가 같은 좌표에 있을 수도 있다.

양은 1초에 거리 1만큼 걷는다. 예를 들어 $(0, 0)$에 있는 양이 $(1, 3)$에 있는 우리로 가려면 약 3.16227766초가 걸리고, 우리가 $(3, 4)$에 있으면 정확히 5초가 걸린다. 양은 모두 동시에 움직이고 서로의 이동을 방해하지 않는다.

모든 양이 우리에 들어가는 데 필요한 최소 시간을 구하라. 즉, 양이 각자 배정된 우리까지 가는 시간 중 가장 큰 값을 최소로 만들어라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 양의 수 $N$, 우리의 수 $M$, 우리 하나에 들어갈 수 있는 양의 최대 수 $K$가 주어진다.

이어지는 $N$개의 줄에는 양의 좌표 $X$와 $Y$가 주어진다.

그다음 $M$개의 줄에는 우리의 좌표 $X$와 $Y$가 주어진다.

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

각 테스트 케이스마다 최소 시간의 제곱을 정수로 한 줄에 출력한다. 좌표가 모두 정수이므로 최소 시간의 제곱은 항상 정수다. 예를 들어 최소 시간이 5초라면 25를 출력한다.