Экономия
Представь, что ты - капитан команды, которая только что выиграла мировой финал 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).
Выходные данные
Для каждого теста в отдельной строке выведите оптимальную стоимость покупки.