牛 Bessie は次の大ヒットになると思うゲーム「Angry Cows」を設計しました。完全に独創的だと信じる内容は、数直線の各点に干し草の束がある一次元の場面へ、パチンコで牛を撃ち込むものです。着地の力で近くの束を爆発させます。牛たちを使ってすべての束を爆発させるのが目標です。

$N$ 個の束が異なる整数位置 $x_1, x_2, \ldots, x_N$ にあります。威力 $R$ で撃った牛が $x$ に着地すると半径 $R$ の爆発が起こり、$x-R \ldots x+R$ 内のすべての束を破壊します。

撃てる牛は $K$ 頭で、全頭同じ威力 $R$ です。この $K$ 頭で全束を爆発させられる $R$ の最小整数値を求めてください。

入力

最初の行は $N$（$1 \leq N \leq 50,000$）と $K$（$1 \leq K \leq 10$）です。残る $N$ 行に整数 $x_1 \ldots x_N$ があり、各々 $0 \ldots 1,000,000,000$ の範囲です。

出力

全束を爆発させるための各牛の最小威力 $R$ を出力してください。

入出力例

入力 1

7 2
20
25
18
8
10
3
1

出力 1

5

問題作成者：Brian Dean