奶牛 Bessie 设计了一款她认为将大受欢迎的电子游戏：“Angry Cows”。她认为完全原创的玩法是，用弹弓把奶牛发射到一维场景中，数轴不同位置放有干草捆。每头奶牛落地的力量足以引爆落点附近的干草捆。目标是用若干奶牛引爆所有干草捆。

数轴上有 $N$ 个干草捆，位于互不相同的整数位置 $x_1, x_2, \ldots, x_N$。若以威力 $R$ 发射奶牛，落在 $x$，就引发半径为 $R$ 的爆炸，摧毁 $x-R \ldots x+R$ 范围内所有干草捆。

共有 $K$ 头奶牛可发射，每头威力同为 $R$。求 $R$ 的最小整数值，使这 $K$ 头奶牛能够引爆所有干草捆。

输入格式

第一行包含 $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