Економія
Уяви, що ти — капітан команди, яка щойно виграла світовий фінал ACM ICPC, і тепер тобі потрібно відсвяткувати свою перемогу зі своїми друзями, яких у тебе рівно k-1. Для цього необхідно придбати n пляшок улюбленого напою (залишається тільки здогадуватися якого) в найближчому магазині. Вартість i-ї пляшки становить c_i гривень. На жаль, продавець не любить, коли його клієнти купують занадто багато пляшок, тому він змінює ціну пляшки для клієнта, який раніше у нього вже робив покупки. Точніше, якщо клієнт вже купив x пляшок, то він повинен заплатити (x+1)·c_i гривень, щоб купити пляшку номер i.
Необхідно визначити мінімально можливу вартість придбання n пляшок з урахуванням того, що в процесі покупки можуть брати участь не більше k осіб (тільки ти і твої друзі).
Вхідні дані
Перша стрічка містить кількість тестів t (t ≤ 100). Кожен тест складається з двох стрічок. Перша стрічка містить два цілих числа n і k (1 ≤ n, k ≤ 100). Друга стрічка містить n додатних цілих чисел c_1, c_2, ..., c_n - відповідні вартості покупок (1 ≤ c_i ≤ 10^6).
Вихідні дані
Для кожного тесту в окремому рядку виведіть оптимальну вартість покупки.