Вам дан массив \(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\) операций, значения всех оставшихся элементов будут прибавлены к вашему счету.
Посчитайте минимально возможный счет, который вы можете получить.
Выходные данные
Выведите одно целое число — минимально возможный счет.
Примечание
Рассмотрим пример из условия.
В первом наборе входных данных можно получить результат, равный \(2\):
- выберем \(a_7 = 1\) и \(a_4 = 2\); счет станет \(0 + \lfloor \frac{1}{2} \rfloor = 0\), а массив станет \([1, 1, 1, 1, 3]\);
- выберем \(a_1 = 1\) и \(a_5 = 3\); счет станет \(0 + \lfloor \frac{1}{3} \rfloor = 0\), а массив станет \([1, 1, 1]\);
- выберем \(a_1 = 1\) и \(a_2 = 1\); счет станет \(0 + \lfloor \frac{1}{1} \rfloor = 1\), а массив станет \([1]\);
- добавим оставшийся элемент \(1\) к счету, и он станет \(2\).
Во втором наборе входных данных вне зависимости от того, как провести операцию, итоговый счет будет равен \(16\).
В третьем наборе входных данных можно получить результат, равный \(0\):
- выберем \(a_1 = 1\) и \(a_2 = 3\); счет станет \(0 + \lfloor \frac{1}{3} \rfloor = 0\), а массив станет \([3, 7]\);
- выберем \(a_1 = 3\) и \(a_2 = 7\); счет станет \(0 + \lfloor \frac{3}{7} \rfloor = 0\), а массив станет пустым;
- массив пуст, поэтому счет больше не меняется.
В четвертом наборе входных данных нельзя выполнить ни одной операции, поэтому итоговый счет равен сумме элементов массива: \(4 + 2 = 6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|