Економія#3927
Ви та ще k-1 ваших друзів хочете купити книжок у магазині. Книжка номер має ціну c_i. Проте продавцю не подобається, коли один покупець купує занадто багато книжок, тому він підвищує ціну для тих, хто купує декілька книжок. Зокрема, якщо покупець вже купив книжок, то щоб купити книжку номер , він повинен заплатити (x+1) \cdot c_i доларів.
Ви та ще k-1 ваших друзів хочете купити всі книжок, розподіляючи покупки між собою так, щоб сума витрачених грошей була мінімальною.
Перший рядок містить кількість тестів (t \leq 100). Кожен тест складається з двох рядків. Перший рядок містить цілі числа та (1 \leq n, k \leq 100). Другий рядок містить додатних цілих чисел c_1, c_2, \ldots, c_n (1 \leq c_i \leq 10^6) — ціни книжок.
Для кожного тесту в окремому рядку виведіть мінімальну суму грошей, необхідну для купівлі всіх книжок.
Приклад 1