K-ary Huffman Encoding

The Huffman language has $N$ characters. Unlike Korea, which uses binary encoding made of 0 and 1, the Huffman language uses $K$-ary encoding made of the digits $0$ through $K - 1$.

We want to encode the Huffman language in $K$-ary. The encoding must satisfy the following conditions.

1. Assign one $K$-ary string to each of the $N$ characters.
2. No assigned string may be a prefix of another assigned string.

For example, the table below shows a valid $3$-ary encoding of the four characters !, @, #, and +.

No string in this table is a prefix of another, so both conditions hold. The next table breaks the first condition, because ! is assigned 013, which uses the digit $3$ and is not valid in base $3$.

The table after that breaks the second condition, because + is a prefix of #.

Given a string in the Huffman language, what is the shortest possible length of its $K$-ary encoding? For example, suppose the string !!!@@@@#####++++++ contains ! 3 times, @ 4 times, # 5 times, and + 6 times. With the first encoding table above, the total length is $54$ ($3 \times 3 + 4 \times 3 + 5 \times 3 + 6 \times 3 = 54$).

The input contains $T$ test cases. The first line contains $T$.

The first line of each test case contains two integers $N$ ($2 \le N \le 10\,000$) and $K$ ($2 \le K \le 10\,000$), separated by a space. $N$ is the number of characters in the Huffman language, and $K$ is the base to encode in. The next line contains $N$ integers $C_i$ ($0 \le C_i \le 100\,000$), separated by spaces. Each $C_i$ is the number of times the $i$-th character appears in the string.

For each test case, print on its own line the minimum possible length of the $K$-ary encoding of the given string.

In both test cases, assigning the following encoding gives the minimum length.

In the first case, the string can be expressed with length $3 + 4 + 3 = 10$. In the second case, it can be expressed with length $3 + 4 + 2 = 9$.