C. Разделение массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть отсортированный массив $$$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$$$ непустых последовательных подотрезков.

Входные данные

Первая строка содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 3 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$ 1 \le a_i \le 10^9$$$, $$$a_i \ge a_{i-1}$$$).

Выходные данные

Выведите минимальную цену, которую вы можете получить, разделив массив $$$a$$$ на $$$k$$$ непустых последовательных подотрезков.

Примеры
Входные данные
6 3
4 8 15 16 23 42
Выходные данные
12
Входные данные
4 4
1 3 3 7
Выходные данные
0
Входные данные
8 1
1 1 2 3 5 8 13 21
Выходные данные
20
Примечание

В первом тестовом примере можо разделить массив $$$a$$$ следующим образом: $$$[4, 8, 15, 16], [23], [42]$$$.