题目描述

桃子有一个包含 $n$ 个整数的数列：$a_1, a_2, \ldots, a_n$。但是她并不是特别喜欢这个数列。

桃子为数列 $a$ 定义了一个美观程度 $c(a)$，它的计算公式如下：

其中 $c(a)$ 越小，数列 $a$ 越美观。

桃子可以选择数列中最多 $k$ 个元素的数值并修改它们的数值（可以修改为任何数值），她希望修改后的 $c(a)$ 尽可能地小。

请你帮助她计算 $c(a)$ 的最小值。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$，以一个空格分隔，分别表示数列大小和最多能够修改的数列中元素个数（$1 \le k \le n \le 2000$）。

输入的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，两两之间以一个空格分隔，表示初始时数列中的每个元素（$-10^9 \le a_i \le 10^9$）。

输出格式

输出一个整数，表示在修改不超过 $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 \le 20$；
• 对于 $40\%$ 的数据，$n \le 200, -1000 \le a_i \le 1000$；
• 对于 $100\%$ 的数据，$1 \le k \le n \le 2000, -10^9 \le a_i \le 10^9$。
• 存在一组数据 $k = n$。