题目描述

将多米诺骨牌按一定间距排列成行，轻轻碰倒第一枚骨牌，其余的骨牌就会产生连锁反应，依次倒下。

为了保证骨牌的连锁反应能够顺利进行下去，相邻两块骨牌的距离应该足够小

但张胖胖干啥啥不行，尝试摆了几次骨牌后，每次都无法掌握好骨牌的间距。

张胖胖气急败坏，想找一个人来帮他摆好骨牌。

于是，倒霉的你被抓来摆放骨牌。

张胖胖首先在直线上固定了 $N$ ($2≤N≤100000$)块骨牌的位置，对于第 $i$ 块骨牌，它在直线上的坐标为 $a_i$ ( $2 \leq a_i \leq 10^{12}$ )。

接下来又给了你 $K$ ( $0 \leq K \leq 100000$ )块可以自由摆放的骨牌，你可以将其摆在直线上没有骨牌的任意位置。

为了使骨牌倒下的连锁反应顺利发生，你要保证你的摆放完成后，相邻的两个骨牌的距离尽可能小。即相邻两块骨牌距离的最大值最小

请将这个最大距离 $L$ 告诉张胖胖

输入格式

第一行输入包含两个整数，

分别是固定的骨牌数量 $N$ ,和可以自由摆放的骨牌数量$K$

第二行输入固定的n个骨牌的坐标$a_1$,$a_2$,…,$a_n$（ $a_i < a_{i+1}$ ）

输出格式

输出包含一个整数，即相邻两块骨牌距离的最大值 $L$

样例

样例输入

2 2
4 106

样例输出

34