Оценка
"Здесь слишком много чисел!" — восклицает ваш начальник. "Как я должен во всем этом разобраться? Уменьшите количество! Оцените!"
Вы расстроены. Создание этих чисел потребовало много усилий. Но вы выполните просьбу начальника.
Вы решаете оценить следующим образом: у вас есть массив A чисел. Вы разделите его на k смежных секций, которые могут быть разного размера. Затем вы используете одно число, чтобы оценить всю секцию. Другими словами, для вашего массива A размера n вы хотите создать другой массив B того же размера, который состоит из k смежных секций. Если i и j находятся в одной секции, то B[i]=B[j]. Ваша цель — минимизировать ошибку, выраженную как сумма абсолютных значений разностей (Σ|A[i]-B[i]|).
Входные данные
Входные данные содержат несколько тестов. Каждый тест начинается с двух целых чисел в одной строке: n (1 ≤ n ≤ 2000) и k (1 ≤ k ≤ 25, k ≤ n), где n — размер массива, а k — количество смежных секций для оценки. Массив A будет представлен на следующих n строках, по одному целому числу на строку. Каждый элемент массива A находится в диапазоне от -10000 до 10000 включительно. Ввод завершается строкой с двумя 0.
Выходные данные
Для каждого теста выведите одно целое число в отдельной строке, которое является минимальной ошибкой, которую вы можете достичь. Не выводите лишние пробелы и не разделяйте ответы пустыми строками. Все возможные входные данные дают ответы, которые помещаются в знаковое целое число 64 бит.