Оцінка
"Тут занадто багато чисел!" - кричить ваш бос. "Як я маю зрозуміти все це? Скороти! Оціни!"
Ви розчаровані. Це вимагало багато зусиль, щоб згенерувати ці числа. Але ви зробите те, що просить ваш бос.
Ви вирішуєте оцінити наступним чином: у вас є масив A чисел. Ви розділите його на k суміжних секцій, які не обов'язково будуть однакового розміру. Потім ви використаєте одне число, щоб оцінити всю секцію. Іншими словами, для вашого масиву A розміру n, ви хочете створити інший масив B розміру n, який має 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-біт.