amazing-race-3

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

NOTE:

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

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

Input Format:

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

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

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

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

Output Format:

Print the minimum time required to end the race.

Constraints:

1 ≤ n ≤ 200

1 ≤ m ≤ 200

1 ≤ k ≤ n

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

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

1 ≤ speed of team ≤ 50

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

SAMPLE OUTPUT
4

Explanation

For the race to finish in the minimum time the team at location (0,1) can reach the checkpoint at (0,10) .The distance between them is 9 and speed of team is 5 so required time is ceil(99))/(55))=ceil(81/25)=4.

Source: hackerearth | Difficulty: MEDIUM
Tags: Sorting


Solutions: