题目描述

给定一个整数序列 $a_1,\dots,a_n$ ，小爱希望通过一系列调整操作使所有数字均相等，但可惜他只有$m$次机会，每次机会可以将序列中任意一个整数更改成他想要的值。

尽管他没有办法让所有的数字在操作后均相等，但他还是想让整个序列看上去更平整一些。于是小爱定义了不平整指数，所谓一个序列的不平整指数，指该序列中任意相邻两元素差值的绝对值的最大值。不平整指数越大，证明存在相邻两项差值绝对值越大，则序列越不平整。

请你帮他计算如何更改$m$次数字，才能使修改后序列的不平整指数最小？

输入格式

输入共两行， 第一行，两个正整数$n,m$ 第二行，$n$个正整数$a_1,a_2,...,a_n$

输出格式

输出修改后序列的最小不平整指数

4 2
1 3 5 7

2

6 2
5 5 2 5 2 5

0

样例解释 2

两次修改都2换成5

数据范围

对于$30\%$的数据，$1 \leq n \leq 10$ 对于$60\%$的数据，$1 \leq n \leq 22$ 对于$100\%$的数据，$1 \leq n \leq 1000$，$0 \leq m \leq n$，$-10^9 \leq a_i \leq 10^9$