题目描述

Kiana所居住的城市打算新开发一片商业区，其中最重要的一个项目是在枫叶大道旁修建起\(n\)栋摩天大楼来，而Kiana则担任起了这个项目的总工程师，负责对这些摩天大楼的高度和美观度进行规划。

每栋摩天大楼的副工程师都向Kiana提交了自己对大楼的初步规划，其中第\(i\)栋大楼的工程师希望大楼的高度为\(H_i\)。大楼自身的高度本来是无所谓的，但是Kiana觉得相邻的大楼高度相差太多会不好看，于是她定义这些大楼的不美观度为相邻两栋大楼高度差的绝对值的最大值，即不美观度\(U=\max_{1\leq i<n}\{|H_i-H_{i+1}|\}\)。

修改副工程师们的规划需要付出一定代价，所以Kiana希望至多选出\(k\)栋大楼来，并分别修改它们的高度，每栋大楼的高度都可以修改成任意正整数，而Kiana想知道自己修改以后最小的不美观度是多少。由于Kiana自己不会算，所以希望你能够帮助她。

输入输出格式

输入格式

第一行包含两个正整数\(n\)和\(k\)，分别表示计划修建的摩天大楼数量，以及Kiana至多可以修改的摩天大楼数量。

第二行包含\(n\)个正整数，其中第\(i\)个数\(H_i\)表示第\(i\)栋摩天大楼初步规划的高度。

输出格式

输出一行一个正整数，表示Kiana修改后最小的不美观度。

输入输出样例

输入样例#1：

5 2
1 2 3 5 6 

输出样例#1：

1

输入样例#2：

planning2.in

输出样例#2：

planning2.ans

样例解释

枫叶大道旁准备修起\(n\)栋摩天大楼，其初步规划的高度依次为\(1,2,3,5,6\)，Kiana至多可以修改\(2\)栋大楼的高度。

Kiana应该将第\(4\)栋大楼的高度改为\(4\)，第\(5\)栋大楼的高度改为\(5\)，修改后摩天大楼的高度依次为\(1,2,3,4,5\)，其不美观度为\(1\)，可以证明这是不美观度最小的方案。

数据范围

对于\(10\%\)的数据，保证\(1\leq n\leq 10,k=1\)。

另有\(10\%\)的数据，保证\(1\leq n\leq 10,1\leq k\leq 10\)。

另有\(10\%\)的数据，保证\(1\leq n\leq 200,k=1\)。

另有\(10\%\)的数据，保证\(1\leq n\leq 200,1\leq k\leq 10\)。

另有\(10\%\)的数据，保证\(1\leq n\leq 200,1\leq k\leq 200\)。

另有\(10\%\)的数据，保证\(1\leq n\leq 2000,k=1\)。

另有\(20\%\)的数据，保证\(1\leq n\leq 2000,1\leq k\leq 10\)。

对于\(100\%\)的数据，保证\(1\leq n\leq 2000,1\leq k\leq n\leq 2000,1\leq H_i\leq 2\times 10^9\)。

此外共有\(20\%\)的数据，保证\(1\leq H_i\leq 10\)。