| Codeforces Round 210 (Div. 1) |
|---|
| Закончено |
У Левко есть массив, состоящий из целых чисел: a1, a2, ... , an. Но этот массив совсем ему не нравится.
Левко считает, что красота массива a напрямую зависит от значения c(a), которое можно посчитать по формуле:
Наступило время перемен, и Левко собирается изменить свой массив к лучшему. Если быть точнее, Левко хочет изменить значения не более k элементов массива (разрешается изменять значения на любые целые). Конечно, в результате изменений массив должен стать как можно более красивым.
Помогите Левко — посчитайте, какого минимального значения c(a) ему удастся достичь.
В первой строке записаны два целых числа n и k (1 ≤ k ≤ n ≤ 2000). Во второй строке через пробел записаны целые числа a1, a2, ... , an ( - 109 ≤ ai ≤ 109).
Единственное число — минимальное значение 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
В первом примере Левко может изменить второй и четвертый элементы и получить массив: 4, 4, 4, 4, 4.
В третьем примере он может получить массив: 1, 2, 3, 4, 5, 6.
