Представь, что ты - капитан команды, которая только что выиграла мировой финал ACM ICPC, и теперь тебе предстоит отпраздновать свою победу со своими друзьями, которых у тебя ровно \textbf{k-1}. Для этого необходимо закупить \textbf{n} бутылок любимого напитка (остается только догадываться какого) в ближайшем магазине. Стоимость \textbf{i}-й бутылки составляет \textbf{c_i} рублей. К сожалению, продавец не любит, когда его клиенты покупают слишком много бутылок, поэтому он изменяет цену бутылки для клиента, который ранее у него уже делал покупки. Точнее, если клиент уже купил \textbf{x} бутылок, то он должен заплатить \textbf{(x+1)·c_i} рублей, чтобы купить бутылку номер \textbf{i}. Необходимо определить минимально возможную стоимость приобретения \textbf{n} бутылок с учетом того, что в процессе покупки могут участвовать не более \textbf{k} человек (только ты и твои друзья). \InputFile Первая строка содержит количество тестов \textbf{t} (\textbf{t} ≤ \textbf{100}). Каждый тест состоит из двух строк. Первая строка содержит два целых числа \textbf{n} и \textbf{k} (\textbf{1} ≤ \textbf{n}, \textbf{k} ≤ \textbf{100}). Вторая строка содержит \textbf{n} положительных целых чисел \textbf{c_1}, \textbf{c_2}, ..., \textbf{c_n} - соответствующие стоимости покупок (\textbf{1} ≤ \textbf{c_i} ≤ \textbf{10^6}). \OutputFile Для каждого теста в отдельной строке выведите оптимальную стоимость покупки.