Statement is not available in English language
C. Торговля
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рынок и торговля — важный аспект цивилизации. Любой достаточно умелый игрок в «Цивилизацию» в какой-то момент достигает этапа игры, когда его склады завалены разнообразием редких ресурсов. И иногда их становится так много, что высчитывать оптимальную цену продажи каждого отдельного ресурса становится невозможно.

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

Более формально, сейчас его цивилизация продает $$$n$$$ товаров, каждый из них имеет свою стоимость $$$s_i$$$, причем все $$$s_i$$$ различны. Необходимо выбрать новые цены для товаров $$$e_i$$$, что

  • все $$$e_i$$$ целые;
  • $$$e_i \ge s_i$$$ для всех $$$i$$$;
  • среди всех $$$e_i$$$ есть в точности $$$k$$$ различных значений (не больше и не меньше);
  • $$$\sum\limits_{i=1}^n (e_i - s_i)$$$ минимальна.

Вам необходимо подобрать такой набор цен, и определить соответвующий ему суммарный прирост цен всех товаров.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке ввода находится одно целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 10^3$$$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ — количество товаров и требуемое количество различных цен, соответственно ($$$1 \leq k \leq n \leq 2 \cdot 10^3$$$).

Вторая строка набора содержит $$$n$$$ целых чисел $$$s_1, s_2, \ldots s_n$$$ — цены товаров ($$$1 \leq s_i \leq 10^9$$$; все $$$s_i$$$ различны).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^3$$$.

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

Для каждого набора входных данных в отдельной строке выведите единственное число — минимальное суммарное повышение цен, соответствующее всем требованиям.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. За $$$N$$$ обозначена сумма $$$n$$$ по всем тестовым случаям.

ПодзадачаБаллыДоп. ограничения Необходимые подзадачи Информация о проверке
0–примеры из условияполная
15$$$N \leq 6, s_i \leq 8$$$первая ошибка
25$$$k = 1$$$первая ошибка
35$$$k = 2$$$первая ошибка
45$$$k = 3$$$первая ошибка
520$$$N \leq 200$$$1первая ошибка
615$$$n - k \leq 100$$$1первая ошибка
745нет0 – 6первая ошибка
Пример
Входные данные
3
4 2
1 2 4 3
7 3
1 5 12 4 11 6 3
9 5
4 6 13 1 3 8 7 12 5
Выходные данные
2
6
4