amazing-race-3_9746
It is the final leg of the most famous amazing race. The top 'n' competitors have made it to the final. The final race has just begun. The race has 'm' checkpoints. Each team can reach any of the 'm' checkpoint but after a team reaches a particular checkpoint that checkpoint gets closed and is not open to any other team. The race ends when 'k' teams finish the race. Each team travel at a constant speed throughout the race which might be different for different teams. Given the coordinates of n teams and m checkpoints and speed of individual team return the value of minimum time needed to end the race.

NOTE:

The time required for a team at coordinate (p,q) with speed 's' to reach a checkpoint at coordinate (x,y) is given by:

t = ceil( ((p-x)^2 + (q-y)^2) / s^2 ). For example if distance is 5 units and speed is 2 units then required time = ceil(25/4) = 7.

Input Format:

The first line contains 3 integers n, m and k denoting the total number of competitors, total number of checkpoints and the minimum number of teams that must complete the race in order to end the race.

This is followed by n lines each indicating the coordinates of n teams.

This is followed by m lines each indicating the coordinates of m checkpoints.

This is followed by n integers each denoting the speed of the ith team

Output Format:

Print the minimum time required to end the race.

Constraints:

1 ≤ n ≤ 200

1 ≤ m ≤ 200

1 ≤ k ≤ n

0 ≤ x coordinate of team and checkpoint ≤10^6

0 ≤ y coordinate of team and checkpoint ≤10^6

1 ≤ speed of team ≤ 50

SAMPLE INPUT
2 3 1
0 1
0 0
0 10
27 29
458 9651
5 3

SAMPLE OUTPUT
4

Explanation

For the race to finish in the minimum time the team at location (0,1) can reach the checkpoint at (0,10) .The distance between them is 9 and speed of team is 5 so required time is ceil(99))/(55))=ceil(81/25)=4.
def possible(time):
	match = [-1 for i in xrange(m)]
	vis = [0 for i in xrange(n)]
	ret, tim = 0, 42
	def dfs(u):
		vis[u] = tim
		for t, i in G[u]:
			if t <= time:
				if match[i] == -1 or (vis[match[i]] != tim and dfs(match[i])):
					match[i] = u
					return True
			else:
				break
		return False
	for i in xrange(n):
		if dfs(i):
			ret += 1
			tim += 1
	return ret

n, m, k = map(int, raw_input().split())
start, end = [], []
for _ in xrange(n):
	start.append(map(int, raw_input().split()))
for _ in xrange(m):
	end.append(map(int, raw_input().split()))
speed = map(int, raw_input().split())

G = []
for i, x in enumerate(start):
	G.append([])
	for j, y in enumerate(end):
		d = (x[0] - y[0]) ** 2 + (x[1] - y[1]) ** 2
		s = speed[i] ** 2
		t = d / s + (1 if d % s else 0)
		G[-1].append((t, j))
		G[-1].sort()

lo, hi = 0, 10 ** 20
while lo < hi:
	mi = (lo + hi) / 2
	if possible(mi) >= k:
		hi = mi
	else:
		lo = mi + 1
print lo
2 3 1
0 1
0 0
0 10
27 29
458 9651
5 3

SAMPLE 2 3 1
0 1
0 0
0 10
27 29
458 9651
5 3

S@MPLE 2 3 0
0 1
0 0
0 10
41 29
458 4196
5 2

S@MPLE 2 3 1
0 0
0 2
2 10
41 26
458 7943
5 4

S@NPLE 2 3 2
0 1
0 2
2 10
41 26
381 7943
5 4

S@NPLE 2 2 1
0 1
0 2
2 10
41 29
458 6028
5 4

S@NPLE 2 3 1
0 1
0 2
1 13
41 26
381 7943
5 4

ELPN@S 2 3 1
0 1
-1 0
0 10
27 29
656 9651
7 3

S@MPLE 2 3 2
0 1
1 0
0 10
11 29
458 4196
5 2

S@LPME 2 3 1
0 1
0 2
3 15
39 29
458 1269
2 4

S@NPLE 2 3 1
0 0
0 2
3 10
41 5
381 7943
7 4

EKPN@S 2 3 1
0 0
0 2
2 18
42 49
458 8998
5 4

S@NPLE 2 3 2
0 1
1 0
-1 10
11 21
458 4196
5 2

S@LPME 2 3 2
0 1
2 0
-1 10
11 21
458 4196
5 2

S@LPLE 2 3 1
0 2
0 1
3 15
39 25
458 1269
2 4

S@NPKE 2 3 1
-1 0
0 2
2 18
68 49
458 8998
5 5

S@NPLE 2 3 2
0 1
2 0
-1 10
11 1
458 4196
5 2

S@LPLE 2 3 1
0 2
0 2
3 15
39 25
458 1269
2 1

S@NPKE 2 3 2
0 1
2 0
-1 10
11 1
458 4196
5 1

S@LPLE 2 3 1
0 2
0 4
5 15
39 25
458 2043
2 1

S@NPEK 2 3 1
0 3
0 4
5 15
39 25
417 3512
2 1

S@NPEK 2 3 1
0 3
0 4
5 28
39 25
417 3512
2 1

S@NPEK 2 3 2
0 1
-1 0
0 10
27 27
656 9651
7 3

S@MPLE 2 3 2
1 1
1 0
0 10
11 29
458 4196
5 2

S@LPME 2 3 2
0 1
0 1
1 10
72 29
458 7943
5 2

S@NPLE 2 3 2
0 1
1 0
-1 10
11 29
458 4196
1 2

S@LPME 2 3 1
0 0
0 2
3 19
41 5
381 19637
7 5

DKPN@S 2 3 2
0 1
2 0
-1 10
14 1
458 4196
5 1

S@LPLE 2 3 2
1 1
1 2
3 10
41 2
381 19637
9 5

DKPN@S 2 3 1
0 0
0 0
0 20
27 29
458 9651
5 3

S@MPLE 2 3 1
0 1
0 0
0 16
27 23
458 9651
5 5

SAMPLE 2 3 2
0 1
-1 2
2 10
41 43
381 7943
5 4

S@NPLE 2 3 2
0 0
0 2
2 10
41 26
389 7943
5 2

S@NPLE 2 3 2
0 1
1 2
2 7
41 35
389 7943
5 4

S@NPLE 2 3 2
1 1
1 0
0 10
11 29
458 4196
3 2

S@LPME 2 3 1
0 -1
0 2
2 18
38 49
458 8998
5 4

S@NPLE 2 3 1
1 1
0 1
0 10
72 29
458 7943
1 1

S@NPLE 2 3 2
0 1
4 0
-1 10
11 21
251 4196
5 2

S@LPLE 2 3 2
0 1
2 0
-1 10
12 1
458 4196
5 1

S@LPLE 2 3 1
0 2
0 7
5 28
39 25
417 3512
2 1

S@NPEK 2 3 2
1 1
1 0
0 10
13 29
458 4196
3 2

S@LPME 2 3 2
0 2
0 1
1 10
72 29
458 7943
5 4

S@NPLE 2 3 1
0 0
0 1
3 18
41 5
381 7943
7 4

EKPN@S 2 3 2
0 1
0 -1
-1 10
75 32
458 4196
5 3

S@MPLE 2 3 1
0 -1
0 2
2 18
38 49
458 8998
2 4

S@NPLE 2 3 2
0 1
1 0
-1 10
11 25
458 4196
1 2

S@LPLD 2 3 1
0 2
0 2
6 15
27 25
458 1269
2 1

S@NQKE 2 3 1
0 3
0 1
5 22
73 25
417 3512
2 1

S@MPEK 2 3 1
0 0
0 0
0 10
41 6
458 4196
2 2

S@MPLE 2 3 2
0 1
-1 2
2 10
35 43
381 2227
5 4

S@NPLE 2 3 2
0 1
-1 0
0 17
27 27
656 6995
7 3

S@MPME 2 3 2
1 0
1 0
-1 10
2 29
458 4196
1 2

S@LPME 2 3 1
0 1
0 1
1 10
72 29
176 7943
3 2

S@NPLE 2 3 1
0 1
0 0
0 10
27 29
458 4196
5 3

S@MPLE 2 3 1
0 1
0 0
0 10
27 29
458 4196
5 2

S@MPLE 2 3 1
0 1
0 0
0 10
41 29
458 4196
5 2

S@MPLE 2 3 0
0 1
0 1
0 10
41 29
458 4196
5 2

S@MPLE 2 3 0
0 1
0 1
0 10
41 29
458 7943
5 2

S@MPLE 2 3 0
0 1
0 2
0 10
41 29
458 7943
5 2

S@MPLE 2 3 0
0 1
0 2
1 10
41 29
458 7943
5 2

S@MPLE 2 3 0
0 1
0 2
1 10
41 29
458 7943
5 2

S@NPLE 2 3 0
0 1
0 2
1 10
41 29
458 7943
5 4

S@NPLE 2 3 1
0 1
0 2
1 10
41 29
458 7943
5 4

S@NPLE 2 3 1
0 1
0 2
2 10
41 29
458 7943
5 4

S@NPLE 2 3 1
0 1
0 2
3 10
41 29
458 7943
5 4

S@NPLE 2 3 1
0 1
0 2
2 10
41 26
458 7943
5 4

S@NPLE 2 3 1
0 1
0 2
2 10
41 26
381 7943
5 4

S@NPLE 2 3 1
0 1
0 2
2 10
41 26
381 7943
5 4

ELPN@S 2 3 1
0 1
0 2
2 10
41 5
381 7943
5 4

ELPN@S 2 3 1
0 1
0 0
0 10
27 23
458 9651
5 3

SAMPLE 2 3 1
0 1
-1 0
0 10
27 29
458 9651
5 3

S@MPLE 2 3 1
0 1
0 0
0 10
27 29
458 4196
5 2

S@LPME 2 3 1
0 1
0 0
0 10
67 29
458 4196
5 2

S@MPLE 2 3 0
0 1
0 0
0 10
41 16
458 4196
5 2

S@MPLE 2 3 0
0 1
1 1
0 10
41 29
458 4196
5 2

S@MPLE 2 3 0
0 1
0 1
0 10
41 51
458 7943
5 2

S@MPLE 2 3 0
0 1
0 2
0 10
41 29
458 7943
5 2

ELPM@S 2 3 0
0 1
0 2
1 6
41 29
458 7943
5 2

S@MPLE 2 3 0
0 1
0 2
1 10
41 29
458 7943
6 2

S@NPLE 2 3 0
0 2
0 2
1 10
41 29
458 7943
5 4

S@NPLE 2 3 1
0 1
0 1
1 10
41 29
458 7943
5 4

S@NPLE 2 3 1
0 1
0 2
2 10
41 29
458 6028
5 4

S@NPLE 2 3 1
0 1
0 2
3 10
39 29
458 7943
5 4

S@NPLE 2 3 1
0 1
0 2
1 10
41 26
381 7943
5 4

ELPN@S 2 3 1
0 1
0 2
2 10
41 5
381 7943
5 4

EKPN@S 2 3 1
0 1
0 0
0 10
42 23
458 9651
5 3

SAMPLE 2 3 1
0 1
-1 0
0 10
27 29
656 9651
5 3

S@MPLE 2 3 1
0 1
1 0
0 10
27 29
458 4196
5 2

S@LPME 2 3 1
0 1
0 0
0 10
67 29
458 4196
5 4

S@MPLE 2 3 0
0 1
0 0
0 18
41 16
458 4196
5 2

S@MPLE 2 3 0
0 1
1 1
0 1
41 29
458 4196
5 2

S@MPLE 2 3 1
0 1
0 1
0 10
41 51
458 7943
5 2

S@MPLE 2 3 1
0 1
0 2
0 10
41 29
458 7943
5 2

ELPM@S 2 3 0
-1 1
0 2
1 6
41 29
458 7943
5 2

S@MPLE 2 3 0
0 2
0 2
1 10
41 29
458 7943
5 4

S@EPLN 2 3 1
0 1
0 1
1 10
58 29
458 7943
5 4

S@NPLE 2 3 1
0 1
0 2
3 10
39 29
458 7943
2 4

S@NPLE 2 3 1
0 0
0 2
2 10
41 49
458 7943
5 4

S@NPLE 2 3 2
0 1
0 2
2 10
41 26
389 7943
5 4

S@NPLE 2 3 1
0 0
0 2
2 10
41 5
381 7943
5 4

EKPN@S 2 3 1
1 1
0 0
0 10
42 23
458 9651
5 3

SAMPLE
4 4
 0
 5
 93
 1
 6
 2
 37
 12
 3
 14
 26
 28
 13
 11
 21
 45
 82
 49
 43
 163
 29
 36
 239
 236
 8
 109
 20
 16
 9
 138
 95
 114
 99
 15
 81
 32
 101
 176
 104
 237
 7
 264
 17
 182
 52
 97
 25
 120
 33
 211
 10
 4
 4
 4
 0
 0
 0
 0
 0
 0
 4
 4
 4
 4
 4
 4
 4
 4
 4
 4
 4
 0
 0
 0
 0
 0
 0
 0
 4
 4
 4
 4
 4
 4
 4
 4
 4
 0
 0
 4
 4
 0
 0
 4
 5
 5
 93
 5
 4
