## USACO 2016 January Contest, Silver

## Problem 1. Angry Cows

Contest has ended.

**Log in to allow submissions in analysis mode**

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.

Contest has ended. No further submissions allowed.
There are $N$ hay bales located at distinct integer positions $x_1, x_2, \ldots, 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 \ldots 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 FORMAT (file angry.in):

The first line of input contains $N$ ($1 \leq N \leq 50,000$) and $K$ ($1 \leq K \leq 10$). The remaining $N$ lines all contain integers $x_1 \ldots x_N$ (each in the range $0 \ldots 1,000,000,000$).#### OUTPUT FORMAT (file angry.out):

Please output the minimum power $R$ with which each cow must be launched in order to detonate all the hay bales.#### SAMPLE INPUT:

7 2 20 25 18 8 10 3 1

#### SAMPLE OUTPUT:

5

Problem credits: Brian Dean