cn03_36617
So, as you all know free WiFis are being 
installed in our institute.
These are a special 
type of WiFi and they start to interfere when 
there is a signal coming from two different 
WiFis at a single location. The WiFi 
installation task is given to you.


There are N suitable locations for the 
installation of WiFi. 
These locations are 
located along straight line positions 
x1,x2,...,xN (0<=xi<=1000000000).
You  have to install C WiFis. 
You have to 
install the WiFis at locations such that the 
minimum distance between any two of them 
is as large as possible.
 What is the largest 
minimum distance ?

 

Input
Line 1 of contains Two space-separated integers: N and C.

Each of the next N lines, contain an integer denoting the 
location Xi.


Output
Print the largest minimum distance in a 
single line.

Constraints

1 ≤ N ≤ 10^5
1 ≤ Xi ≤ 10^9

 

Example
Input:
5 3
1
2
8
4
9

Output:
3
 

Explanation
Example case 1. The WiFis can be installed at locations 1,4 and 8 or 1,4 and 9 resulting in a minimum distance of 3.
def f(d, N, C, X):

	cows_placed = 1
	last_pos = X[0]
	for i in xrange(1, N):
		if X[i] - last_pos >= d:
			cows_placed += 1
			last_pos = X[i]
			if cows_placed == C:
				return 1

	return 0

N, C = map(int, raw_input().split())

X = []
for i in xrange(N):
	X.append(input())

X.sort()

start = 0
end = X[N-1]

while start < end:

	mid = (start+end)/2
	val = f(mid, N, C, X)

	if val == 1:
		start = mid+1
	else: #if val == 0:
		end = mid

print start-1
5 3
1
2
8
4
9
3