题目描述

奶牛贝西（$\red{Bessie the cow）}$设计了一款她认为将成为下一款热门视频游戏的游戏："愤怒的奶牛"。

她认为这是完全原创的前提，即玩家用弹弓将奶牛射入一维场景，该场景由位于数字线上不同点的一组干草捆组成。

每头奶牛着陆时都有足够的力量引爆靠近其着陆点的干草捆。目标是使用一组奶牛引爆所有干草捆。

有$\red{N}$个干草捆位于数字行上不同的整数位置$\red{x1，}$$\red{x2，…}$，$\red{xN}$。

如果奶牛在动力$\red{R}$着陆位置$\red{x}$的情况下下水，这将导致"半径$\red{R}$"爆炸，摧毁$\red{x}$范围内的所有干草捆$\red{R...}$、 $\red{x+Rx}$。

共有$\red{K}$头奶牛可以拍摄，每头奶牛的$\red{R}$功率相同。

请确定$\red{R}$的最小整数值，以便可以使用$\red{K}$奶牛引爆场景中的每个干草捆。

输入格式

第一行输入包含$\red{N（}$$\red{1≤}$$\red{N≤}$$\red{50,000）}$和$\red{K（}$$\red{1≤}$$\red{K≤}$$\red{10). }$其余的$\red{N}$行都包含整数$\red{x1…}$$\red{xN}$（每个在$\red{0…}$$\red{100000000}$）。

输出格式

请输出每头奶牛必须启动的最小功率$\red{R，}$以引爆所有干草捆。

样例

输入样例

7 2
20
25
18
8
10
3
1

输出样例

5