Angry Cows (Silver)
Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, which she believes is completely original, is that the player shoots cows with a slingshot into a one-dimensional scene consisting of a set of hay bales located at various points on a number line. Each cow lands with sufficient force to detonate the hay bales in close proximity to her landing site. The goal is to use a set of cows to detonate all the hay bales.
There are n hay bales located at distinct integer positions x[1], x[2], ... , x[n] on the number line. If a cow is launched with power r landing at position x, this will causes a blast of "radius r", destroying all hay bales within the range x − r ... x + r.
A total of k cows are available to shoot, each with the same power r. Please determine the minimum integer value of r such that it is possible to use the k cows to detonate every single hay bale in the scene.
Input
The first line contains n (1 ≤ n ≤ 50000) and k (1 ≤ k ≤ 10). The remaining n lines all contain integers x[1] ... x[n] (each in the range 0 ... 10^9).
Output
Print the minimum power r with which each cow must be launched in order to detonate all the hay bales.