2.3 Wolf Placement in the Forest 🐺

Score: 20pts

Time Limit: 5.00 sec

Zoya is tasked with placing a number of wild wolves into scattered cages in a dark forest. The cages are unevenly distributed, and she needs to place the wolves in such a way that the minimum distance between any two wolves is maximised. The forest is dangerous, and placing wolves too close to each other could lead to chaos.

Given n cages placed at specific positions in a forest (represented as an array of integers arr[]), and k wolves to be placed in these cages, find the maximum possible minimum distance betwe

en any two wolves when placed optimally.

Given n cages placed at specific positions in a forest (represented as an array of integers arr[]), and k wolves to be placed in these cages, find the maximum possible minimum distance betwe

en any two wolves when placed optimally.

Constraints

2≤n≤10^5

2≤k≤n

0≤arr[i]≤10^9

2≤k≤n

0≤arr[i]≤10^9

Input Format

The first line contains two integers n (the number of cages) and k (the number of wolves).

The second line contains n space-separated integers, representing the positions of the cages.

The second line contains n space-separated integers, representing the positions of the cages.

Output Format

Output a single integer, which is the maximum possible minimum distance between any two wolves.

Example 1

Input:

6 4

0 3 4 7 10 9

Output:

3

Explanation:

The maximum possible minimum distance between any two wolves is 3 when 4 wolves are placed at positions {0, 3, 7, 10}. The distances between wolves are 3, 4, and 3, respectively.

6 4

0 3 4 7 10 9

Output:

3

Explanation:

The maximum possible minimum distance between any two wolves is 3 when 4 wolves are placed at positions {0, 3, 7, 10}. The distances between wolves are 3, 4, and 3, respectively.