eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Экономия

Экономия

Лимит времени 5 секунд
Лимит использования памяти 256 MiB

Представь, что ты - капитан команды, которая только что выиграла мировой финал ACM ICPC, и теперь тебе предстоит отпраздновать свою победу со своими друзьями, которых у тебя ровно k-1. Для этого необходимо закупить n бутылок любимого напитка (остается только догадываться какого) в ближайшем магазине. Стоимость i-й бутылки составляет c_i рублей. К сожалению, продавец не любит, когда его клиенты покупают слишком много бутылок, поэтому он изменяет цену бутылки для клиента, который ранее у него уже делал покупки. Точнее, если клиент уже купил x бутылок, то он должен заплатить (x+1)·c_i рублей, чтобы купить бутылку номер i.

Необходимо определить минимально возможную стоимость приобретения n бутылок с учетом того, что в процессе покупки могут участвовать не более k человек (только ты и твои друзья).

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

Первая строка содержит количество тестов t (t100). Каждый тест состоит из двух строк. Первая строка содержит два целых числа n и k (1n, k100). Вторая строка содержит n положительных целых чисел c_1, c_2, ..., c_n - соответствующие стоимости покупок (1c_i10^6).

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

Для каждого теста в отдельной строке выведите оптимальную стоимость покупки.

Пример

Входные данные #1
1
3 3
2 5 6
Выходные данные #1
13
Источник ACM ICPC 2012-2013, NEERC, Krasnojarsk