У вас есть отсортированный массив \(a_1, a_2, \dots, a_n\) (для любого индекса \(i > 1\) выполняется условие \(a_i \ge a_{i-1}\)) и число \(k\).
Вам нужно разделить этот массив на \(k\) непустых последовательных подотрезков. Каждый элемент должен принадлежать ровно одному подотрезку.
Пусть \(max(i)\) будет равно максимуму в \(i\)-м подотрезке, а \(min(i)\) будет равно минимуму в \(i\)-м подотрезке. Тогда цена разделения будет равна \(\sum\limits_{i=1}^{k} (max(i) - min(i))\). Например, если массив \(a = [2, 4, 5, 5, 8, 11, 19]\) и мы разделили его на \(3\) подотрезка следующим образом: \([2, 4], [5, 5], [8, 11, 19]\), тогда цена разделения будет равна \((4 - 2) + (5 - 5) + (19 - 8) = 13\).
Посчитайте минимальную цену разделения массива \(a\) на \(k\) непустых последовательных подотрезков.
Выходные данные
Выведите минимальную цену, которую вы можете получить, разделив массив \(a\) на \(k\) непустых последовательных подотрезков.
Примечание
В первом тестовом примере можо разделить массив \(a\) следующим образом: \([4, 8, 15, 16], [23], [42]\).