In the city of Techville, there are N bikers and M parked bikes, each positioned on a 2D grid. For the annual Velocity Challenge, only K bikers will be allowed to participate.
Ayaan, who’s organizing the event, wants to begin the race as early as possible. Every biker moves at a unit speed, and a bike can be taken by only one biker. Each biker can move freely in any direction.
To minimize the preparation time, Prerana must assign bikers to bikes so that the K fastest bikers can each get to a unique bike, and the maximum travel time among them is minimized.
Your task is to compute the square of the minimum possible time (in terms of distance²), that allows exactly K bikers to get a bike.
Constraints
1 ≤ K ≤ min(N, M)
1 ≤ N, M ≤ 10³
Coordinates are integers with absolute values ≤ 10⁶
Input Format
The first line contains three integers:
N — number of bikers
M — number of bikes
K — number of bikers who will participate
The next N lines each contain two integers — the coordinates of a biker (x, y).
The following M lines each contain two integers — the coordinates of a bike (x, y).
Output Format
Output a single integer — the square of the minimum required time to start the race.
Example 1
Input:
3 3 2
0 1
0 2
0 3
100 1
200 2
300 3
Output:
40000
Explanation:
Explanation
Biker at (0,1) → Bike at (100,1) → distance = 100
Biker at (0,2) → Bike at (200,2) → distance = 200
The second biker is the slowest among the two chosen, taking 200 units of time.
Thus, the square of the required time = 200² = 40000.
Log In to solve the Question