There are $N$ bikers present in a city (shaped as a grid) having $\mbox{M}$ bikes. All the bikers want to participate in the HackerRace competition, but unfortunately only $\mbox{K}$ bikers can be accommodated in the race. Jack is organizing the HackerRace and wants to start the race as soon as possible. He can instruct any biker to move towards any bike in the city. In order to minimize the time to start the race, Jack instructs the bikers in such a way that the first $\mbox{K}$ bikes are acquired in the minimum time.

Every biker moves with a unit speed and one bike can be acquired by only one biker. A biker can proceed in any direction. Consider distance between bikes and bikers as Euclidean distance.

Jack would like to know the square of required time to start the race as soon as possible. 

Input Format

The first line contains three integers, $N$, $\mbox{M}$, and $\mbox{K}$, separated by a single space. 

The following $N$ lines will contain $N$ pairs of integers denoting the co-ordinates of $N$ bikers. Each pair of integers is separated by a single space. The next $\mbox{M}$ lines will similarly denote the co-ordinates of the $\mbox{M}$ bikes.

Constraints

$1\leq N\leq250$ 

$1\leq M\leq250$ 

$1\leq K\leq min(N,M)$ 

$0\leq x_i$, $y_i$ $\leq10$$7$

Output Format

A single line containing the square of required time.

Sample Input
3 3 2
0 1
0 2
0 3
100 1
200 2 
300 3

Sample Output
40000

Explanation

There's need for two bikers for the race. The first biker (0,1) will be able to reach the first bike (100,1) in 100 time units. The second biker (0,2) will be able to reach the second bike (200,2) in 200 time units. This is the most optimal solution and will take 200 time units. So output will be 200^{2} = 40000.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Complete search


Solutions:
def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


import sys
NIL = 0
MAX_INT = 1000000000000000

def bfs(n1matching, n2matching, n1adj, n2adj):
	queue = []
	dist = [MAX_INT] * len(n1matching)
	for i in range(1, len(n1matching)):
		if n1matching[i] == NIL:
			dist[i] = 0
			queue.append(i)
	while len(queue) > 0:
		v = queue.pop()
		if dist[v] < dist[NIL]:
			for u in n1adj[v]:
				if dist[n2matching[u]] == MAX_INT:
					dist[n2matching[u]] = dist[v] + 1
					queue.append(n2matching[u])
	return (dist[NIL] != MAX_INT, dist)

def dfs(v, n1adj, dist, n1matching, n2matching):
	if v != NIL:
		for u in n1adj[v]:
			if dist[n2matching[u]] == dist[v] + 1:
				if dfs(n2matching[u], n1adj, dist, n1matching, n2matching):
					n2matching[u] = v
					n1matching[v] = u
					return True
		dist[v] = MAX_INT
		return False
	return True

def hk(graph, matching_limit):
	(N1, N2, n1adj, n2adj) = graph
	n1matching = [NIL] * (N1 + 1)
	n2matching = [NIL] * (N2 + 1)
	matching_count = 0
	while True:
		(result, dist) = bfs(n1matching, n2matching, n1adj, n2adj)
		if not result:
			break
		for v in range(1, N1 + 1):
			if n1matching[v] == NIL:
				if dfs(v, n1adj, dist, n1matching, n2matching):
					matching_count += 1
					if matching_count >= matching_limit:
						return True
	return False

def construct_bipartite_graph(N, M, dists, dist_limit):
	n1adj = []
	n2adj = []
	for i in range(N + 1):
		n1adj.append([])
	for i in range(M + 1):
		n2adj.append([])
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			if dists[i][j] <= dist_limit:
				n1adj[i].append(j)
				n2adj[j].append(i)
	return (N, M, n1adj, n2adj)

def node_dist(n1, n2):
	return (n1[0] - n2[0]) * (n1[0] - n2[0]) + (n1[1] - n2[1]) * (n1[1] - n2[1])

def try_dist_limit(N, M, K, dists, dist_limit):
	graph = construct_bipartite_graph(N, M, dists, dist_limit)
	return hk(graph, K)

def bike_racers():
	(N, M, K) = [int(x) for x in sys.stdin.readline().split()]
	racers = []
	for _ in range(N):
		(x1, x2) = [int(x) for x in sys.stdin.readline().split()]
		racers.append((x1, x2))
	bikes = []
	for _ in range(M):
		(x1, x2) = [int(x) for x in sys.stdin.readline().split()]
		bikes.append((x1, x2))
	dists = []
	for _ in range(N + 1):
		dists.append([-1] * (M + 1))
	total_dists = set()
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			dists[i][j] = node_dist(racers[i - 1], bikes[j - 1])
			total_dists.add(dists[i][j])
	total_dists = sorted(list(total_dists))
	low = 0
	up = len(total_dists) - 1
	while low < up:
		mid = int((low + up) / 2)
		if try_dist_limit(N, M, K, dists, total_dists[mid]):
			up = mid
		else:
			low = mid + 1
	if try_dist_limit(N, M, K, dists, total_dists[min(up, low)]):
		return total_dists[min(up, low)]
	else:
		return total_dists[max(up, low)]
print(bike_racers())


from itertools import chain

def Match_Size(Edges):
	(S, T, M) = (set(), set(), set())
	G = {}
	TrG = {}
	for (dist, start, end) in Edges:
		S.add(start)
		T.add(end)
		if start not in G:
			G[start] = []
		G[start].append(end)
		if end not in G:
			G[end] = []
		if end not in TrG:
			TrG[end] = []
		TrG[end].append(start)
		if start not in TrG:
			TrG[start] = []
	while S:
		s = S.pop()
		(Q, P) = ({s}, {})
		while Q:
			u = Q.pop()
			if u in T:
				T.remove(u)
				break
			forw = (v for v in G[u] if (u, v) not in M)
			back = (v for v in TrG[u] if (v, u) in M)
			for v in chain(forw, back):
				if v in P:
					continue
				P[v] = u
				Q.add(v)
		while u != s:
			(u, v) = (P[u], u)
			if v in G[u]:
				M.add((u, v))
			else:
				M.remove((v, u))
	return len(M)
(N, M, K) = map(int, input().split())
a = []
b = []
for n in range(N):
	(y, x) = map(int, input().split())
	a.append((n, y, x))
for m in range(M):
	(y, x) = map(int, input().split())
	b.append((m, y, x))
c = []
for (n, y1, x1) in a:
	for (m, y2, x2) in b:
		dist = (y2 - y1) ** 2 + (x2 - x1) ** 2
		c.append((dist, n, N + m))
c = sorted(c)
lo = 0
hi = len(c) - 1
while lo < hi:
	mid = (hi + lo) // 2
	match_size = Match_Size(c[:mid + 1])
	if match_size >= K:
		hi = mid
	else:
		lo = mid + 1
print(c[lo][0])


from math import *
data = input().strip().split(' ')
N = int(data[0])
M = int(data[1])
K = int(data[2])

class Pose(object):

	def __init__(self, xy):
		self.x = float(xy[0])
		self.y = float(xy[1])

	def __str__(self):
		return str([self.x, self.y])

	def __add__(self, other):
		return Pose([self.x + other.x, self.y + other.y])

	def __sub__(self, other):
		return Pose([self.x - other.x, self.y - other.y])

	def norm(self):
		return int(pow(self.x, 2) + pow(self.y, 2))

class Dist(object):

	def __init__(self, dist, bike, biker):
		self.dist = dist
		self.bike = bike
		self.biker = biker

class Biker(object):

	def __init__(self, pose, ID):
		self.ID = ID
		self.pose = pose
		self.possible_bikes = []
		self.waiting_bikes = []
		self.taken_bike = None
		self.pushable = False

	def take_bike(self, bike):
		bike.biker = self
		self.taken_bike = bike
		self.possible_bikes.append(bike)
		for bike in self.waiting_bikes:
			bike.remove_waiting_biker(self)
		self.waiting_bikes = []

	def switch_bike(self, bike):
		self.taken_bike.biker = None
		bike.biker = self
		self.taken_bike = bike

	def add_possible_bike(self, bike):
		self.possible_bikes.append(bike)
		if len(self.possible_bikes) > 1:
			self.pushable = True
		if not self.has_a_bike():
			self.waiting_bikes.append(bike)
			bike.add_waiting_biker(self)

	def is_pushable(self):
		return self.pushable

	def has_a_bike(self):
		if self.taken_bike is None:
			return False
		else:
			return True

	def try_push(self, tried_bikes, bike=None):
		tried_bikes[self.taken_bike.ID] = True
		if bike is not None:
			if bike.biker.pushable:
				if bike.biker.try_push(tried_bikes):
					self.switch_bike(bike)
					return True
		else:
			for bike in self.possible_bikes:
				if tried_bikes[bike.ID]:
					continue
				if bike.is_free():
					self.switch_bike(bike)
					return True
				if bike.biker.pushable:
					if bike.biker.try_push(tried_bikes):
						self.switch_bike(bike)
						return True
			return False

class Bike(object):

	def __init__(self, pose, ID):
		self.ID = ID
		self.pose = pose
		self.waiting_bikers = []
		self.possible_bikers = []
		self.biker = None

	def add_waiting_biker(self, biker):
		self.waiting_bikers.append(biker)

	def remove_waiting_biker(self, biker):
		self.waiting_bikers.pop(self.waiting_bikers.index(biker))

	def is_free(self):
		if self.biker is None:
			return True
		else:
			return False

	def find_waiting_biker(self, tried_bikes, biker_start=None):
		tried_bikes[self.ID] = True
		if biker_start is None:
			if len(self.waiting_bikers) > 0:
				return [self.ID]
			for biker in self.possible_bikers:
				if tried_bikes[biker.taken_bike.ID]:
					continue
				ret_val = biker.taken_bike.find_waiting_biker(tried_bikes)
				if ret_val is not None:
					ret_val.insert(0, self.ID)
					return ret_val
			return None
		else:
			ret_val = biker_start.taken_bike.find_waiting_biker(tried_bikes)
			if ret_val is not None:
				ret_val.insert(0, self.ID)
				return ret_val
			return None

def get_dist(biker, bike):
	return Dist((bike.pose - biker.pose).norm(), bike, biker)

def main(DEBUG=False):
	biker_list = []
	for i in range(0, N):
		biker_list.append(Biker(Pose(input().strip().split(' ')), i))
	bike_list = []
	for i in range(0, M):
		bike_list.append(Bike(Pose(input().strip().split(' ')), i))
	dist_list = []
	for biker in biker_list:
		for bike in bike_list:
			dist_list.append(get_dist(biker, bike))
	dist_list = sorted(dist_list, key=lambda dist: dist.dist)
	verif_list = [[] for bike in bike_list]
	count = 0
	conte = 0
	for dist in dist_list:
		conte += 1
		bike = dist.bike
		biker = dist.biker
		if DEBUG:
			print(bike.ID)
			print(biker.ID)
			print([b.ID for b in bike_list[0].waiting_bikers])
		bike.possible_bikers.append(biker)
		verif_list[bike.ID].append(biker.ID)
		if bike.is_free():
			if biker.has_a_bike():
				biker.add_possible_bike(bike)
				tried_bikes = [False for bike in bike_list]
				ret_val = bike.find_waiting_biker(tried_bikes, biker)
				if ret_val is not None:
					waiting_biker = bike_list[ret_val[len(ret_val) - 1]].waiting_bikers[0]
					taken_bike = bike_list[ret_val[len(ret_val) - 1]]
					for i in range(0, len(ret_val) - 1):
						biker = bike_list[ret_val[i + 1]].biker
						if biker is not None:
							biker.switch_bike(bike_list[ret_val[i]])
					waiting_biker.take_bike(taken_bike)
					count += 1
				else:
					pass
			else:
				biker.take_bike(bike)
				count += 1
		elif biker.has_a_bike():
			biker.add_possible_bike(bike)
			tried_bikes = [False for bike in bike_list]
			ret_val = bike.find_waiting_biker(tried_bikes, biker)
			if ret_val is not None:
				waiting_biker = bike_list[ret_val[len(ret_val) - 1]].waiting_bikers[0]
				taken_bike = bike_list[ret_val[len(ret_val) - 1]]
				tried_bikes = [False for bike in bike_list]
				if biker.try_push(tried_bikes, bike):
					for i in range(0, len(ret_val) - 1):
						biker = bike_list[ret_val[i + 1]].biker
						if biker is not None:
							biker.switch_bike(bike_list[ret_val[i]])
					waiting_biker.take_bike(taken_bike)
					count += 1
			else:
				pass
		else:
			tried_bikes = [False for bike in bike_list]
			if bike.biker.try_push(tried_bikes):
				biker.take_bike(bike)
				count += 1
			else:
				pass
			biker.add_possible_bike(bike)
		if count >= K:
			print(dist.dist)
			if DEBUG:
				lname = []
				for biker in biker_list:
					if not biker.has_a_bike():
						lname.append(biker.ID)
				print(lname)
				n = 20
				print([dist.bike.ID for dist in dist_list])
				print([dist.biker.ID for dist in dist_list])
				print([dist.dist for dist in dist_list])
				for bike in bike_list:
					if bike.biker is None:
						for biker_id in lname:
							for biker_id2 in verif_list[bike.ID]:
								if biker_id == biker_id2:
									print('yes')
						print(bike.ID, -1, bike.waiting_bikers, verif_list[bike.ID])
						for ID in verif_list[bike.ID]:
							if biker_list[ID].has_a_bike():
								pass
							else:
								print('found you')
					else:
						print(bike.ID, bike.biker.ID, [biker.ID for biker in bike.waiting_bikers], verif_list[bike.ID])
						pass
			break
main(False)


import collections
import math
Coord = collections.namedtuple('Coord', 'x y')
Edge = collections.namedtuple('Edge', 'node distance')

def read_input():
	(riders, bikes, max_participants) = get_int_list(input())
	(rider_list, bike_list) = ({}, {})
	for i in range(riders):
		rider_list[i] = Coord(*get_float_list(input()))
	for i in range(bikes):
		bike_list[i + riders] = Coord(*get_float_list(input()))
	return (max_participants, rider_list, bike_list)

class BfsNode:

	def __init__(self, node_id):
		self.id = node_id
		self.parent = None
		self.distance = None
		self.visited = False

	def visit(self, parent, distance):
		self.parent = parent
		self.distance = distance
		self.visited = True

class CountPairs:

	def __init__(self, first_list: list, second_list: list):
		self.source = max(max(first_list), max(second_list)) + 1
		self.sink = self.source + 1
		self.node_list = first_list + second_list
		self.node_list.extend([self.source, self.sink])
		self.capacity = {x: {} for x in self.node_list}
		self.flow = {x: {} for x in self.node_list}
		self.residual = {x: set() for x in self.node_list}
		for to_node in first_list:
			self.add_edge(self.source, to_node)
		for from_node in second_list:
			self.add_edge(from_node, self.sink)

	def add_edge(self, from_node, to_node):
		if to_node not in self.capacity[from_node]:
			self.capacity[from_node][to_node] = 1
			self.flow[from_node][to_node] = 0
			self.residual[from_node].add(to_node)

	def bfs(self):
		node_list = {node_id: BfsNode(node_id) for node_id in self.node_list}
		my_queue = collections.deque()
		node_list[self.source].distance = 0
		node_list[self.source].visited = True
		my_queue.append(node_list[self.source])
		while len(my_queue) > 0:
			my_node = my_queue.popleft()
			for next_node_id in self.residual[my_node.id]:
				if not node_list[next_node_id].visited:
					node_list[next_node_id].visit(my_node.id, node_list[my_node.id].distance + 1)
					if next_node_id == self.sink:
						my_queue.clear()
						break
					my_queue.append(node_list[next_node_id])
		my_node = node_list[self.sink]
		if my_node.parent is None:
			return []
		path = collections.deque()
		path.appendleft(my_node.id)
		while my_node.parent is not None:
			my_node = node_list[my_node.parent]
			path.appendleft(my_node.id)
		return list(path)

	def add_path(self, path):
		for i in range(len(path) - 1):
			from_node = path[i]
			to_node = path[i + 1]
			if to_node in self.flow[from_node]:
				self.flow[from_node][to_node] = 1
			else:
				self.flow[to_node][from_node] = 0
			self.residual[from_node].remove(to_node)
			self.residual[to_node].add(from_node)

	def calculate_pairs(self):
		while True:
			path = self.bfs()
			if len(path) == 0:
				return sum(self.flow[self.source].values())
			self.add_path(path)

class BikeRacer:

	def __init__(self):
		(self.max_participants, self.riders_list, self.bike_list) = read_input()
		self.distances = self.calculate_distances()
		self.count_pairs = CountPairs(list(self.riders_list.keys()), list(self.bike_list.keys()))

	def calculate_distances(self):
		distances = []
		for (i_rider, rider) in self.riders_list.items():
			for (i_bike, bike) in self.bike_list.items():
				distance = math.sqrt((rider.x - bike.x) ** 2 + (rider.y - bike.y) ** 2)
				distances.append((distance, i_rider, i_bike))
		return sorted(distances)

	def calculate_min_time(self):
		bike_d = collections.defaultdict(set)
		i_pointer = 0
		distance = 0
		while len(bike_d) < self.max_participants or self.count_pairs.calculate_pairs() < self.max_participants:
			(distance, rider, bike) = self.distances[i_pointer]
			self.count_pairs.add_edge(rider, bike)
			bike_d[bike].add(rider)
			i_pointer += 1
		return distance

	def calculate(self):
		return round(self.calculate_min_time() ** 2)

def get_independent_set_count(bike_d):
	count = 0
	already_used = set()
	for rider_set in bike_d.values():
		if len(rider_set.difference(already_used)) > 0:
			count += 1
		already_used.update(rider_set)
	return count

def main():
	my_obj = BikeRacer()
	print(my_obj.calculate())

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]

def get_float_list(in_str):
	return [float(i) for i in in_str.strip().split()]
main()


import time

def PrintM(Mat, N, M):
	for i1 in range(N):
		for i2 in range(M):
			print(Mat[i1, i2], '  ', end='')
		print('')
	print('')

class Graph:

	def __init__(self, graph):
		self.graph = graph
		self.ppl = len(graph)
		self.jobs = len(graph[0])

	def bpm(self, u, matchR, seen):
		for v in range(self.jobs):
			if self.graph[u][v] and seen[v] == False:
				seen[v] = True
				if matchR[v] == -1 or self.bpm(matchR[v], matchR, seen):
					matchR[v] = u
					return True
		return False

	def maxBPM(self):
		matchR = [-1] * self.jobs
		result = 0
		for i in range(self.ppl):
			seen = [False] * self.jobs
			if self.bpm(i, matchR, seen):
				result += 1
		return result
(N, M, K) = [int(m) for m in input().strip().split()]
RiderList = []
BikeList = []
for i in range(N):
	(X, Y) = [int(m) for m in input().strip().split()]
	RiderList.append((X, Y))
for i in range(M):
	(X, Y) = [int(m) for m in input().strip().split()]
	BikeList.append((X, Y))
DistSq = {}
DistMax = 0
DistMin = 10000000000.0
for i1 in range(N):
	for i2 in range(M):
		DiSq = (RiderList[i1][0] - BikeList[i2][0]) ** 2 + (RiderList[i1][1] - BikeList[i2][1]) ** 2
		DistSq[i1, i2] = DiSq
		if DiSq > DistMax:
			DistMax = DiSq
		if DiSq < DistMin:
			DistMin = DiSq
if DistMax == 0:
	print(0)
else:
	st = time.time()
	left = [DistMin - 1, 0]
	right = [DistMax, min(N, M)]
	for Tempi in range(40):
		Cutoff = (left[0] + right[0]) // 2
		bpGraph = [[0 for i1 in range(N)] for i2 in range(M)]
		for i1 in range(N):
			for i2 in range(M):
				if DistSq[i1, i2] <= Cutoff:
					bpGraph[i2][i1] = 1
		g = Graph(bpGraph)
		nPair = g.maxBPM()
		if nPair >= K:
			right = [Cutoff, nPair]
		else:
			left = [Cutoff, nPair]
		if right[0] - left[0] == 1:
			break
	print(int(right[0]))


INF = 1 << 31

def BFS(Adj, Dist, Pair_U, Pair_V, U, V, n):
	Q = []
	for u in U:
		if Pair_U[u] == n:
			Dist[u] = 0
			Q.append(u)
		else:
			Dist[u] = INF
	Dist[n] = INF
	while len(Q) > 0:
		u = Q.pop()
		if Dist[u] < Dist[n]:
			for v in Adj[u]:
				if Dist[Pair_V[v]] == INF:
					Dist[Pair_V[v]] = Dist[u] + 1
					Q.append(Pair_V[v])
	return Dist[n] != INF

def DFS(Adj, Dist, Pair_V, Pair_U, u, n):
	if u != n:
		for v in Adj[u]:
			if Dist[Pair_V[v]] == Dist[u] + 1:
				if DFS(Adj, Dist, Pair_V, Pair_U, Pair_V[v], n) == True:
					Pair_V[v] = u
					Pair_U[u] = v
					return True
		Dist[u] = INF
		return False
	return True

def HopcroftKarp(Adj, n, m):
	U = [i for i in range(n)]
	V = [i for i in range(m)]
	Pair_U = [n for u in U]
	Pair_V = [n for v in V]
	Dist = [0 for i in range(n + 1)]
	matching = 0
	while BFS(Adj, Dist, Pair_U, Pair_V, U, V, n) == True:
		for u in U:
			if Pair_U[u] == n:
				if DFS(Adj, Dist, Pair_V, Pair_U, u, n) == True:
					matching += 1
	return matching

def getDistance(x, y, u, v):
	dx = x - u
	dy = y - v
	return dx * dx + dy * dy

def addEdges(Adj, distances, lo, hi):
	for i in range(lo, hi + 1):
		(dist, u, v) = distances[i]
		Adj[v].add(u)

def removeEdges(Adj, distances, lo, hi):
	for i in range(hi + 1, lo, -1):
		(dist, u, v) = distances[i]
		Adj[v].remove(u)

def binarySearch(distances, Adj, n, m, k):
	low = 0
	high = len(distances) - 1
	mid = int((low + high) / 2)
	addEdges(Adj, distances, low, mid)
	while low <= high:
		HK = HopcroftKarp(Adj, n, m)
		if HK >= k:
			high = mid - 1
			mid = int((low + high) / 2)
			removeEdges(Adj, distances, mid, high)
		else:
			low = mid + 1
			mid = int((low + high) / 2)
			addEdges(Adj, distances, low, mid)
	print(distances[mid + 1][0])

def main():
	(n, m, k) = map(int, input().rstrip().split(' '))
	Adj = [set() for i in range(n)]
	bikers = []
	distances = []
	for i in range(n):
		(x, y) = map(int, input().rstrip().split(' '))
		bikers.append([x, y])
	for i in range(m):
		(u, v) = map(int, input().rstrip().split(' '))
		for j in range(n):
			(x, y) = bikers[j]
			distances.append([getDistance(x, y, u, v), i, j])
	distances = sorted(distances, key=lambda x: x[0])
	binarySearch(distances, Adj, n, m, k)
main()


import sys
from collections import deque
lines = sys.stdin.readlines()
n = int(lines[0].split()[0])
m = int(lines[0].split()[1])
k = int(lines[0].split()[2])
lines.pop(0)
bikers = []
bikes = []
for i in range(n):
	bikers.append((int(lines[i].split()[0]), int(lines[i].split()[1])))
for i in range(n, n + m):
	bikes.append((int(lines[i].split()[0]), int(lines[i].split()[1])))

def calcdist(i, j):
	(x, y) = bikers[i]
	(w, z) = bikes[j]
	return (x - w) ** 2 + (y - z) ** 2

def checkfeasible(dist, k):
	resid = {}
	neighbors = {}
	for i in range(n + m):
		neighbors[i] = []
	for i in range(n):
		for j in range(m):
			if calcdist(i, j) <= dist:
				resid[i, n + j] = 1
				resid[n + j, i] = 0
				neighbors[i].append(n + j)
				neighbors[n + j].append(i)
	neighbors[-1] = []
	neighbors[-2] = []
	for i in range(n):
		resid[-1, i] = 1
		resid[i, -1] = 0
		neighbors[i].append(-1)
		neighbors[-1].append(i)
	for i in range(n, n + m):
		resid[i, -2] = 1
		resid[-2, i] = 0
		neighbors[i].append(-2)
		neighbors[-2].append(i)
	matches = 0
	while matches < k:
		queue = deque([-1])
		parent = {-1: None}
		found = False
		while len(queue) > 0:
			node = queue.popleft()
			for i in neighbors[node]:
				if i not in parent and resid[node, i] == 1:
					parent[i] = node
					queue.append(i)
					if i == -2:
						queue = deque()
						found = True
						nn = -2
						while nn != -1:
							resid[parent[nn], nn] += -1
							resid[nn, parent[nn]] += 1
							nn = parent[nn]
						matches += 1
						break
		if not found:
			return False
	return True
low = 0
high = 1
while not checkfeasible(high, k):
	high = high * 2
while low != high:
	mid = int((low + high) / 2)
	if checkfeasible(mid, k):
		high = mid
	else:
		low = mid + 1
print(low)


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from itertools import chain

def Match_Size(Edges):
	(S, T, M) = (set(), set(), set())
	G = {}
	TrG = {}
	for (dist, start, end) in Edges:
		S.add(start)
		T.add(end)
		if start not in G:
			G[start] = []
		G[start].append(end)
		if end not in G:
			G[end] = []
		if end not in TrG:
			TrG[end] = []
		TrG[end].append(start)
		if start not in TrG:
			TrG[start] = []
	while S:
		s = S.pop()
		(Q, P) = ({s}, {})
		while Q:
			u = Q.pop()
			if u in T:
				T.remove(u)
				break
			forw = (v for v in G[u] if (u, v) not in M)
			back = (v for v in TrG[u] if (v, u) in M)
			for v in chain(forw, back):
				if v in P:
					continue
				P[v] = u
				Q.add(v)
		while u != s:
			(u, v) = (P[u], u)
			if v in G[u]:
				M.add((u, v))
			else:
				M.remove((v, u))
	return len(M)
(N, M, K) = map(int, input().split())
a = []
b = []
for n in range(N):
	(y, x) = map(int, input().split())
	a.append((n, y, x))
for m in range(M):
	(y, x) = map(int, input().split())
	b.append((m, y, x))
c = []
for (n, y1, x1) in a:
	for (m, y2, x2) in b:
		dist = (y2 - y1) ** 2 + (x2 - x1) ** 2
		c.append((dist, n, N + m))
c = sorted(c)
lo = 0
hi = len(c) - 1
while lo < hi:
	mid = (hi + lo) // 2
	match_size = Match_Size(c[:mid + 1])
	if match_size >= K:
		hi = mid
	else:
		lo = mid + 1
print(c[lo][0])


import sys
NIL = 0
MAX_INT = 1000000000000000

def bfs(n1matching, n2matching, n1adj, n2adj):
	queue = []
	dist = [MAX_INT] * len(n1matching)
	for i in range(1, len(n1matching)):
		if n1matching[i] == NIL:
			dist[i] = 0
			queue.append(i)
	while len(queue) > 0:
		v = queue.pop()
		if dist[v] < dist[NIL]:
			for u in n1adj[v]:
				if dist[n2matching[u]] == MAX_INT:
					dist[n2matching[u]] = dist[v] + 1
					queue.append(n2matching[u])
	return (dist[NIL] != MAX_INT, dist)

def dfs(v, n1adj, dist, n1matching, n2matching):
	if v != NIL:
		for u in n1adj[v]:
			if dist[n2matching[u]] == dist[v] + 1:
				if dfs(n2matching[u], n1adj, dist, n1matching, n2matching):
					n2matching[u] = v
					n1matching[v] = u
					return True
		dist[v] = MAX_INT
		return False
	return True

def hk(graph, matching_limit):
	(N1, N2, n1adj, n2adj) = graph
	n1matching = [NIL] * (N1 + 1)
	n2matching = [NIL] * (N2 + 1)
	matching_count = 0
	while True:
		(result, dist) = bfs(n1matching, n2matching, n1adj, n2adj)
		if not result:
			break
		for v in range(1, N1 + 1):
			if n1matching[v] == NIL:
				if dfs(v, n1adj, dist, n1matching, n2matching):
					matching_count += 1
					if matching_count >= matching_limit:
						return True
	return False

def construct_bipartite_graph(N, M, dists, dist_limit):
	n1adj = []
	n2adj = []
	for i in range(N + 1):
		n1adj.append([])
	for i in range(M + 1):
		n2adj.append([])
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			if dists[i][j] <= dist_limit:
				n1adj[i].append(j)
				n2adj[j].append(i)
	return (N, M, n1adj, n2adj)

def node_dist(n1, n2):
	return (n1[0] - n2[0]) * (n1[0] - n2[0]) + (n1[1] - n2[1]) * (n1[1] - n2[1])

def try_dist_limit(N, M, K, dists, dist_limit):
	graph = construct_bipartite_graph(N, M, dists, dist_limit)
	return hk(graph, K)

def bike_racers():
	(N, M, K) = [int(x) for x in sys.stdin.readline().split()]
	racers = []
	for _ in range(N):
		(x1, x2) = [int(x) for x in sys.stdin.readline().split()]
		racers.append((x1, x2))
	bikes = []
	for _ in range(M):
		(x1, x2) = [int(x) for x in sys.stdin.readline().split()]
		bikes.append((x1, x2))
	dists = []
	for _ in range(N + 1):
		dists.append([-1] * (M + 1))
	total_dists = set()
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			dists[i][j] = node_dist(racers[i - 1], bikes[j - 1])
			total_dists.add(dists[i][j])
	total_dists = sorted(list(total_dists))
	low = 0
	up = len(total_dists) - 1
	while low < up:
		mid = int((low + up) / 2)
		if try_dist_limit(N, M, K, dists, total_dists[mid]):
			up = mid
		else:
			low = mid + 1
	if try_dist_limit(N, M, K, dists, total_dists[min(up, low)]):
		return total_dists[min(up, low)]
	else:
		return total_dists[max(up, low)]
print(bike_racers())


import sys
NIL = 0
MAX_INT = 1000000000000000

def bfs(n1matching, n2matching, n1adj, n2adj):
	queue = []
	dist = [MAX_INT] * len(n1matching)
	for i in range(1, len(n1matching)):
		if n1matching[i] == NIL:
			dist[i] = 0
			queue.append(i)
	while len(queue) > 0:
		v = queue.pop()
		if dist[v] < dist[NIL]:
			for u in n1adj[v]:
				if dist[n2matching[u]] == MAX_INT:
					dist[n2matching[u]] = dist[v] + 1
					queue.append(n2matching[u])
	return (dist[NIL] != MAX_INT, dist)

def dfs(v, n1adj, dist, n1matching, n2matching):
	if v != NIL:
		for u in n1adj[v]:
			if dist[n2matching[u]] == dist[v] + 1:
				if dfs(n2matching[u], n1adj, dist, n1matching, n2matching):
					n2matching[u] = v
					n1matching[v] = u
					return True
		dist[v] = MAX_INT
		return False
	return True

def hk(graph, matching_limit):
	(N1, N2, n1adj, n2adj) = graph
	n1matching = [NIL] * (N1 + 1)
	n2matching = [NIL] * (N2 + 1)
	matching_count = 0
	while True:
		(result, dist) = bfs(n1matching, n2matching, n1adj, n2adj)
		if not result:
			break
		for v in range(1, N1 + 1):
			if n1matching[v] == NIL:
				if dfs(v, n1adj, dist, n1matching, n2matching):
					matching_count += 1
					if matching_count >= matching_limit:
						return True
	return False

def construct_bipartite_graph(N, M, dists, dist_limit):
	n1adj = []
	n2adj = []
	for i in range(N + 1):
		n1adj.append([])
	for i in range(M + 1):
		n2adj.append([])
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			if dists[i][j] <= dist_limit:
				n1adj[i].append(j)
				n2adj[j].append(i)
	return (N, M, n1adj, n2adj)

def node_dist(n1, n2):
	return (n1[0] - n2[0]) * (n1[0] - n2[0]) + (n1[1] - n2[1]) * (n1[1] - n2[1])

def try_dist_limit(N, M, K, dists, dist_limit):
	graph = construct_bipartite_graph(N, M, dists, dist_limit)
	return hk(graph, K)

def bike_racers():
	(N, M, K) = [int(x) for x in sys.stdin.readline().split()]
	racers = []
	for _ in range(N):
		(x1, x2) = [int(x) for x in sys.stdin.readline().split()]
		racers.append((x1, x2))
	bikes = []
	for _ in range(M):
		(x1, x2) = [int(x) for x in sys.stdin.readline().split()]
		bikes.append((x1, x2))
	dists = []
	for _ in range(N + 1):
		dists.append([-1] * (M + 1))
	total_dists = set()
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			dists[i][j] = node_dist(racers[i - 1], bikes[j - 1])
			total_dists.add(dists[i][j])
	total_dists = sorted(list(total_dists))
	low = 0
	up = len(total_dists) - 1
	while low < up:
		mid = int((low + up) / 2)
		if try_dist_limit(N, M, K, dists, total_dists[mid]):
			up = mid
		else:
			low = mid + 1
	if try_dist_limit(N, M, K, dists, total_dists[min(up, low)]):
		return total_dists[min(up, low)]
	else:
		return total_dists[max(up, low)]
print(bike_racers())


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


import time

def PrintM(Mat, N, M):
	for i1 in range(N):
		for i2 in range(M):
			print(Mat[i1, i2], '  ', end='')
		print('')
	print('')

class Graph:

	def __init__(self, graph):
		self.graph = graph
		self.ppl = len(graph)
		self.jobs = len(graph[0])

	def bpm(self, u, matchR, seen):
		for v in range(self.jobs):
			if self.graph[u][v] and seen[v] == False:
				seen[v] = True
				if matchR[v] == -1 or self.bpm(matchR[v], matchR, seen):
					matchR[v] = u
					return True
		return False

	def maxBPM(self):
		matchR = [-1] * self.jobs
		result = 0
		for i in range(self.ppl):
			seen = [False] * self.jobs
			if self.bpm(i, matchR, seen):
				result += 1
		return result
(N, M, K) = [int(m) for m in input().strip().split()]
RiderList = []
BikeList = []
for i in range(N):
	(X, Y) = [int(m) for m in input().strip().split()]
	RiderList.append((X, Y))
for i in range(M):
	(X, Y) = [int(m) for m in input().strip().split()]
	BikeList.append((X, Y))
DistSq = {}
DistMax = 0
DistMin = 10000000000.0
for i1 in range(N):
	for i2 in range(M):
		DiSq = (RiderList[i1][0] - BikeList[i2][0]) ** 2 + (RiderList[i1][1] - BikeList[i2][1]) ** 2
		DistSq[i1, i2] = DiSq
		if DiSq > DistMax:
			DistMax = DiSq
		if DiSq < DistMin:
			DistMin = DiSq
if DistMax == 0:
	print(0)
else:
	st = time.time()
	left = [DistMin - 1, 0]
	right = [DistMax, min(N, M)]
	for Tempi in range(40):
		Cutoff = (left[0] + right[0]) // 2
		bpGraph = [[0 for i1 in range(N)] for i2 in range(M)]
		for i1 in range(N):
			for i2 in range(M):
				if DistSq[i1, i2] <= Cutoff:
					bpGraph[i2][i1] = 1
		g = Graph(bpGraph)
		nPair = g.maxBPM()
		if nPair >= K:
			right = [Cutoff, nPair]
		else:
			left = [Cutoff, nPair]
		if right[0] - left[0] == 1:
			break
	print(int(right[0]))


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from itertools import chain

def Match_Size(Edges):
	(S, T, M) = (set(), set(), set())
	G = {}
	TrG = {}
	for (dist, start, end) in Edges:
		S.add(start)
		T.add(end)
		if start not in G:
			G[start] = []
		G[start].append(end)
		if end not in G:
			G[end] = []
		if end not in TrG:
			TrG[end] = []
		TrG[end].append(start)
		if start not in TrG:
			TrG[start] = []
	while S:
		s = S.pop()
		(Q, P) = ({s}, {})
		while Q:
			u = Q.pop()
			if u in T:
				T.remove(u)
				break
			forw = (v for v in G[u] if (u, v) not in M)
			back = (v for v in TrG[u] if (v, u) in M)
			for v in chain(forw, back):
				if v in P:
					continue
				P[v] = u
				Q.add(v)
		while u != s:
			(u, v) = (P[u], u)
			if v in G[u]:
				M.add((u, v))
			else:
				M.remove((v, u))
	return len(M)
(N, M, K) = map(int, input().split())
a = []
b = []
for n in range(N):
	(y, x) = map(int, input().split())
	a.append((n, y, x))
for m in range(M):
	(y, x) = map(int, input().split())
	b.append((m, y, x))
c = []
for (n, y1, x1) in a:
	for (m, y2, x2) in b:
		dist = (y2 - y1) ** 2 + (x2 - x1) ** 2
		c.append((dist, n, N + m))
c = sorted(c)
lo = 0
hi = len(c) - 1
while lo < hi:
	mid = (hi + lo) // 2
	match_size = Match_Size(c[:mid + 1])
	if match_size >= K:
		hi = mid
	else:
		lo = mid + 1
print(c[lo][0])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


import sys
NIL = 0
MAX_INT = 1000000000000000

def bfs(n1matching, n2matching, n1adj, n2adj):
	queue = []
	dist = [MAX_INT] * len(n1matching)
	for i in range(1, len(n1matching)):
		if n1matching[i] == NIL:
			dist[i] = 0
			queue.append(i)
	while len(queue) > 0:
		v = queue.pop()
		if dist[v] < dist[NIL]:
			for u in n1adj[v]:
				if dist[n2matching[u]] == MAX_INT:
					dist[n2matching[u]] = dist[v] + 1
					queue.append(n2matching[u])
	return (dist[NIL] != MAX_INT, dist)

def dfs(v, n1adj, dist, n1matching, n2matching):
	if v != NIL:
		for u in n1adj[v]:
			if dist[n2matching[u]] == dist[v] + 1:
				if dfs(n2matching[u], n1adj, dist, n1matching, n2matching):
					n2matching[u] = v
					n1matching[v] = u
					return True
		dist[v] = MAX_INT
		return False
	return True

def hk(graph, matching_limit):
	(N1, N2, n1adj, n2adj) = graph
	n1matching = [NIL] * (N1 + 1)
	n2matching = [NIL] * (N2 + 1)
	matching_count = 0
	while True:
		(result, dist) = bfs(n1matching, n2matching, n1adj, n2adj)
		if not result:
			break
		for v in range(1, N1 + 1):
			if n1matching[v] == NIL:
				if dfs(v, n1adj, dist, n1matching, n2matching):
					matching_count += 1
					if matching_count >= matching_limit:
						return True
	return False

def construct_bipartite_graph(N, M, dists, dist_limit):
	n1adj = []
	n2adj = []
	for i in range(N + 1):
		n1adj.append([])
	for i in range(M + 1):
		n2adj.append([])
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			if dists[i][j] <= dist_limit:
				n1adj[i].append(j)
				n2adj[j].append(i)
	return (N, M, n1adj, n2adj)

def node_dist(n1, n2):
	return (n1[0] - n2[0]) * (n1[0] - n2[0]) + (n1[1] - n2[1]) * (n1[1] - n2[1])

def try_dist_limit(N, M, K, dists, dist_limit):
	graph = construct_bipartite_graph(N, M, dists, dist_limit)
	return hk(graph, K)

def bike_racers():
	(N, M, K) = [int(x) for x in sys.stdin.readline().split()]
	racers = []
	for _ in range(N):
		(x1, x2) = [int(x) for x in sys.stdin.readline().split()]
		racers.append((x1, x2))
	bikes = []
	for _ in range(M):
		(x1, x2) = [int(x) for x in sys.stdin.readline().split()]
		bikes.append((x1, x2))
	dists = []
	for _ in range(N + 1):
		dists.append([-1] * (M + 1))
	total_dists = set()
	for i in range(1, N + 1):
		for j in range(1, M + 1):
			dists[i][j] = node_dist(racers[i - 1], bikes[j - 1])
			total_dists.add(dists[i][j])
	total_dists = sorted(list(total_dists))
	low = 0
	up = len(total_dists) - 1
	while low < up:
		mid = int((low + up) / 2)
		if try_dist_limit(N, M, K, dists, total_dists[mid]):
			up = mid
		else:
			low = mid + 1
	if try_dist_limit(N, M, K, dists, total_dists[min(up, low)]):
		return total_dists[min(up, low)]
	else:
		return total_dists[max(up, low)]
print(bike_racers())


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


import math
import os
import random
import re
import sys

def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])
{'mode': 'full', 'isActive': False}


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


import math
import os
import random
import re
import sys
from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


import math
import os
import random
import re
import sys

def bipartiteMatch(graph):
	matching = {}
	for u in graph:
		for v in graph[u]:
			if v not in matching:
				matching[v] = u
				break
	while 1:
		preds = {}
		unmatched = []
		pred = dict([(u, unmatched) for u in graph])
		for v in matching:
			del pred[matching[v]]
		layer = list(pred)
		while layer and (not unmatched):
			newLayer = {}
			for u in layer:
				for v in graph[u]:
					if v not in preds:
						newLayer.setdefault(v, []).append(u)
			layer = []
			for v in newLayer:
				preds[v] = newLayer[v]
				if v in matching:
					layer.append(matching[v])
					pred[matching[v]] = v
				else:
					unmatched.append(v)
		if not unmatched:
			unlayered = {}
			for u in graph:
				for v in graph[u]:
					if v not in preds:
						unlayered[v] = None
			return (matching, list(pred), list(unlayered))

		def recurse(v):
			if v in preds:
				L = preds[v]
				del preds[v]
				for u in L:
					if u in pred:
						pu = pred[u]
						del pred[u]
						if pu is unmatched or recurse(pu):
							matching[v] = u
							return 1
			return 0
		for v in unmatched:
			recurse(v)

def main():
	(N, M, K) = map(int, input().split())
	bikers = []
	bikes = []
	for i in range(N):
		(a, b) = map(int, input().split())
		bikers.append((a, b))
	for i in range(M):
		(a, b) = map(int, input().split())
		bikes.append((a, b))
	edges = []
	for (a, b) in bikers:
		for (c, d) in bikes:
			dist = (a - c) ** 2 + (b - d) ** 2
			edges.append((dist, (a, b), (c, d)))
	edges = sorted(edges, reverse=True)
	removed_bikers = 0
	removed_bikes = 0
	biker_hits = dict([(biker, 0) for biker in bikers])
	bike_hits = dict([(bike, 0) for bike in bikes])
	bikers = set(bikers)
	bikes = set(bikes)
	neighbors = dict([(biker, set([bike for bike in bikes])) for biker in bikers])
	G = dict([(biker, neighbors[biker]) for biker in bikers])
	(matching, A, B) = bipartiteMatch(G)
	matching_pairs = set([(bike, matching[bike]) for bike in matching])
	for (dist, biker, bike) in edges:
		biker_hits[biker] += 1
		bike_hits[bike] += 1
		neighbors[biker].remove(bike)
		if (bike, biker) in matching_pairs:
			G = dict([(biker, neighbors[biker]) for biker in bikers])
			(matching, A, B) = bipartiteMatch(G)
			matching_pairs = set([(bike, matching[bike]) for bike in matching])
			if len(matching.keys()) < K:
				print(dist)
				break
		if biker_hits[biker] == M:
			bikers.remove(biker)
main()


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])


from collections import deque
debug = False

def show(matrix):
	if False:
		for row in matrix:
			print(str(row))

def cost(r, b):
	dx = b[0] - r[0]
	dy = b[1] - r[1]
	return dx * dx + dy * dy

def check(limit):
	rtob = {r: [b for b in range(m) if c[r][b] <= limit] for r in range(n)}
	btor = {b: [r for r in range(m) if c[r][b] <= limit] for b in range(m)}
	assd_r = {}
	assd_b = {}
	assd = 0
	arb = False
	assdnow = True
	while assdnow:
		if debug:
			print('Looping through')
		assdnow = False
		for r in range(n):
			if r not in assd_r:
				paths = deque()
				visited_r = set()
				visited_r.add(r)
				for b in reversed(rtob[r]):
					paths.append([(r, b)])
				while paths:
					path = paths.pop()
					(rc, b) = path[-1]
					if b not in assd_b:
						if debug:
							print('assigning', path)
						for (rc, b) in path:
							assd_r[rc] = b
							assd_b[b] = rc
						assd += 1
						if assd >= k:
							if debug:
								print('Success! Assigned %d nodes of %d' % (assd, k))
							return True
						assdnow = True
						break
					else:
						if debug:
							print('continuing', path)
						rc = assd_b[b]
						if rc not in visited_r:
							visited_r.add(rc)
							for bc in reversed(rtob[rc]):
								if b != bc:
									np = path[:]
									np.append((rc, bc))
									paths.append(np)
	if debug:
		print('Failure! Assigned %d nodes of %d' % (assd, k))
	return False
(n, m, k) = map(int, input().split())
rs = [tuple(map(int, input().split())) for _ in range(n)]
bs = [tuple(map(int, input().split())) for _ in range(m)]
c = [[cost(r, b) for b in bs] for r in rs]
show(c)
segs = sorted([c[r][b] for r in range(n) for b in range(m)])
lo = 0
hi = len(segs) - 1
while lo < hi:
	mid = (hi + lo) // 2
	if debug:
		print('examining (%d,%d,%d) (%d)' % (lo, mid, hi, segs[mid]))
	if check(segs[mid]):
		hi = mid
	else:
		lo = mid + 1
print(segs[lo])