You are the captain of a team that has just won World Final ACM ICPC and you have to celebrate your victory now. You gather \textbf{k-1} friends and go to the nearest store to buy \textbf{n} bottles of \[here may be your advertisement!\]. Bottle number i has price \textbf{c_i}. Unfortunately the seller does not like his customers to buy too many bottles, so he changes the price of bottle for a customer who had already bought them before. More precisely, if a customer has already bought \textbf{x} bottles, he has to pay \textbf{(x+1)·c_i} dollars to buy bottle number \textbf{i}. You and your \textbf{k-1} friends want to buy all \textbf{n} bottles in such a way that you spend the as little money as possible. \InputFile The first line consists the number of test cases \textbf{t} (\textbf{t} ≤ \textbf{100}). Each test consists of two lines. First line contains two integers \textbf{n} and \textbf{k} (\textbf{1} ≤ \textbf{n}, \textbf{k} ≤ \textbf{100}). Second line contains \textbf{n }positive integers \textbf{c_1}, \textbf{c_2}, ..., \textbf{c_N} respectively (\textbf{1} ≤ \textbf{c_i} ≤ \textbf{10^6}). \OutputFile For each test case print in a separate line the minimum amount of money you (and your friends) have to pay in order to buy all the \textbf{n} bottles.