Levko 有一个由整数组成的数组:a1、a2、...、an。但他根本不喜欢这个阵法。
Levko认为数组a的美观直接取决于值c(a),可以通过以下公式计算:
$$$$
是时候改变世界了,列夫科将改变他的阵型,使其变得更好。准确地说,Levko 想要更改最多 k 个数组元素的值(允许用任意整数替换值)。当然,改变应该使数组尽可能漂亮。
帮助 Levko 计算他可以达到的最小数字 c(a)。
输入
第一行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 2000)。第二行包含空格分隔的整数 a1, a2, ... , an (- 109 ≤ ai ≤ 109)。
输出
单个数字 — Levko 可以获得的 c(a) 最小值。
示例
输入 #1
5 2 4 7 4 7 4
输出 #1
0
输入 #2
3 1 -100 0 100
输出 #2
100
输入 #3
6 3 1 2 3 7 8 9
输出 #3
1
注意
在第一个示例中,Levko 可以更改第二个和第四个元素并得到数组:4, 4, 4, 4, 4。
在第三个示例中,他可以获得数组:1,2,3,4,5,6。