题目描述
桃子有一个包含 n 个整数的数列:a1,a2,…,an。但是她并不是特别喜欢这个数列。
桃子为数列 a 定义了一个美观程度 c(a),它的计算公式如下:
![](http://oj.hetao101.com/d/training/file/480/oiqr6lzi.png)
其中 c(a) 越小,数列 a 越美观。
桃子可以选择数列中最多 k 个元素的数值并修改它们的数值(可以修改为任何数值),她希望修改后的 c(a) 尽可能地小。
请你帮助她计算 c(a) 的最小值。
输入格式
输入的第一行包含两个整数 n 和 k,以一个空格分隔,分别表示数列大小和最多能够修改的数列中元素个数(1≤k≤n≤2000)。
输入的第二行包含 n 个整数 a1,a2,…,an,两两之间以一个空格分隔,表示初始时数列中的每个元素(−109≤ai≤109)。
输出格式
输出一个整数,表示在修改不超过 k 的元素的情况下 c(a) 能够变成的最小值。
样例
5 2
4 7 4 7 4
0
3 1
-100 0 100
100
6 3
1 2 3 7 8 9
1
样例解释
- 样例1中,可以将数列修改为 4,4,4,4,4;
- 样例2中,可以选择不修改(因为及时修改一个元素也不能让 c(a) 变小);
- 样例3中,可以将数列修改为 1,2,3,4,5,6。
数据范围
- 对于 20% 的数据,n≤20;
- 对于 40% 的数据,n≤200,−1000≤ai≤1000;
- 对于 100% 的数据,1≤k≤n≤2000,−109≤ai≤109。
- 存在一组数据 k=n。