题目描述

在运动会上,小 H 从数轴的原点开始向正方向立定跳远。项目设置了n个检查点 a_i 且a_i>=a_i-1>0。小 H 必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时,小 H 可以自行再增加 m 个检查点让自己跳得更轻松。

在运动会前,小 H 制定训练计划让自己单次跳跃的最远距离达到L,并且学会一个爆发技能可以在运动会时使用一次,使用时可以在该次跳跃时的最远距离变为2L。

小 H 想知道,L的最小值是多少可以完成这个项目?

输入描述

每组测试数据描述如下：

第一行为两个正整数 n , m ( 2 <= n <= 10⁵ ) (2 <= m <= 10⁸)

第二行 n 个正整数 a_i ( 1 <= a_i <= 10⁸ )

输出描述

输出共 1 行，一个整数表示答案。

样例

5 3
1 3 5 16 21

3

样例说明

增加检查点 10,13,19，因此每次跳跃距离为 1,2,2,5,3,3,3,2，在第三次跳跃时使用技能即可。

限制范围

每个测试样例限制为1s, 248Mb。