← 返回题目列表

Codeforces · 360/B

B. Levko 和阵列

中文机器翻译题面 查看原题

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。