Optimal Tree Planting

You are given n planting points along a road and you need to plant m trees. Your task is to choose m points from the given n points, such that the minimum distance between any two planted trees is as large as possible.

Input: The first line contains two integers n and m. The second line contains n integers representing the positions of the planting points in any order. You may assume that the positions are non-negative integers.

Output: Output a single integer representing the maximum possible minimum distance between any two planted trees when placed optimally.

Note: It is guaranteed that there is at least one valid way to plant the trees. A binary search strategy along with a greedy verification algorithm is typically used to solve this problem.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
p1 p2 ... pn

Here, n denotes the number of planting points, m denotes the number of trees to be planted, and p1, p2, ..., pn denote the positions of the planting points.

outputFormat

Output a single integer to standard output (stdout) which represents the maximum minimum distance possible between any two planted trees.

5 3
1 2 8 4 9

3