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

Дан массив A, состоящий из n целых чисел, и целое положительное число k. Массив A проиндексирован целыми числами от 1 до n.

Требуется переставить элементы массива таким образом, чтобы величина

стала минимально возможной. В частности, разрешается не переставлять элементы массива вовсе.
Входные данные

В первой строке заданы два целых числа n, k (2 ≤ n ≤ 3·105, 1 ≤ k ≤ min(5000, n - 1)).

Во второй строке следуют n целых чисел A[1], A[2], ..., A[n] ( - 109 ≤ A[i] ≤ 109), разделенных пробелами — элементы массива A.

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

Выведите минимальное возможное значение суммы, описанной в условии задачи.

Примеры
Входные данные
3 2
1 2 4
Выходные данные
1
Входные данные
5 2
3 -5 3 -5 3
Выходные данные
0
Входные данные
6 3
4 3 4 3 2 5
Выходные данные
3
Примечание

В первом тесте одна из оптимальных перестановок имеет вид 1 4 2.

Во втором тесте исходная перестановка является оптимальной.

В третьем тесте одна из оптимальных перестановок имеет вид 2 3 4 4 3 5.