페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3956

Angry Cows 2초 512MB

문제

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, \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.

Problem credits: Brian Dean


입력

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).


출력

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


예제1

입력
7 2
20
25
18
8
10
3
1
출력
5

출처

USACO 2016 January Silver

역링크 공식 문제집만