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

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел, и еще одно целое число $$$k$$$, удовлетворяющее условию $$$2k \le n$$$.

Вы должны выполнить ровно $$$k$$$ операций с этим массивом. В каждой операции вы должны выбрать два элемента массива (пусть эти элементы — $$$a_i$$$ и $$$a_j$$$; они могут быть как одинаковыми, так и различными, но это должны быть элементы на разных позициях), удалить их из массива и прибавить $$$\lfloor \frac{a_i}{a_j} \rfloor$$$ к своему счету, где $$$\lfloor \frac{x}{y} \rfloor$$$ обозначает максимальное целое число, не превосходящее $$$\frac{x}{y}$$$.

Изначально ваш счет равен $$$0$$$. После того как вы выполните ровно $$$k$$$ операций, значения всех оставшихся элементов будут прибавлены к вашему счету.

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

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк. В первой строке заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 100$$$; $$$0 \le k \le \lfloor \frac{n}{2} \rfloor$$$).

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$).

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

Выведите одно целое число — минимально возможный счет.

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

Рассмотрим пример из условия.

В первом наборе входных данных можно получить результат, равный $$$2$$$:

  1. выберем $$$a_7 = 1$$$ и $$$a_4 = 2$$$; счет станет $$$0 + \lfloor \frac{1}{2} \rfloor = 0$$$, а массив станет $$$[1, 1, 1, 1, 3]$$$;
  2. выберем $$$a_1 = 1$$$ и $$$a_5 = 3$$$; счет станет $$$0 + \lfloor \frac{1}{3} \rfloor = 0$$$, а массив станет $$$[1, 1, 1]$$$;
  3. выберем $$$a_1 = 1$$$ и $$$a_2 = 1$$$; счет станет $$$0 + \lfloor \frac{1}{1} \rfloor = 1$$$, а массив станет $$$[1]$$$;
  4. добавим оставшийся элемент $$$1$$$ к счету, и он станет $$$2$$$.

Во втором наборе входных данных вне зависимости от того, как провести операцию, итоговый счет будет равен $$$16$$$.

В третьем наборе входных данных можно получить результат, равный $$$0$$$:

  1. выберем $$$a_1 = 1$$$ и $$$a_2 = 3$$$; счет станет $$$0 + \lfloor \frac{1}{3} \rfloor = 0$$$, а массив станет $$$[3, 7]$$$;
  2. выберем $$$a_1 = 3$$$ и $$$a_2 = 7$$$; счет станет $$$0 + \lfloor \frac{3}{7} \rfloor = 0$$$, а массив станет пустым;
  3. массив пуст, поэтому счет больше не меняется.

В четвертом наборе входных данных нельзя выполнить ни одной операции, поэтому итоговый счет равен сумме элементов массива: $$$4 + 2 = 6$$$.