K진 Huffman 인코딩

Huffman 나라의 문자는 $N$개로 이루어져 있다. 0과 1로 된 이진 인코딩이 발달한 대한민국과 달리, Huffman 나라에서는 $0$부터 $K - 1$까지의 숫자로 이루어진 $K$진법 인코딩이 발달했다.

우리는 Huffman 나라의 언어를 $K$진법으로 인코딩하려 한다. 이때 다음 조건을 만족해야 한다.

1. $N$개의 각 문자에 $K$진법 문자열을 하나씩 배정해야 한다.
2. 배정된 $K$진법 문자열 중 어떤 것도 다른 문자열의 접두사가 될 수 없다.

예를 들어 아래 표는 !, @, #, + 네 문자를 $3$진법으로 올바르게 인코딩한 것이다.

각 문자열이 서로의 접두사가 아니므로 두 조건을 모두 만족한다. 다음 표는 !에 013을 배정했으므로 첫 번째 조건을 만족하지 않는다.

그다음 표는 +이 #의 접두사이므로 두 번째 조건을 만족하지 않는다.

Huffman 나라의 언어로 된 문자열이 하나 주어졌을 때, 이 문자열을 $K$진법으로 인코딩한 결과의 최소 길이는 얼마인가? 예를 들어 문자열 !!!@@@@#####++++++에서 !가 3번, @가 4번, #가 5번, +가 6번 나타난다고 하자. 위의 첫 번째 인코딩 표를 적용하면 전체 길이는 $54$가 된다 ($3 \times 3+4\times 3+5\times 3+6\times 3 = 54$).

입력은 $T$개의 테스트 케이스로 구성된다. 첫 줄에는 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $N$ ($2 \le N \le 10\,000$)과 $K$ ($2 \le K \le 10\,000$)가 공백으로 구분되어 주어진다. $N$은 Huffman 나라의 문자 수이고, $K$는 인코딩할 진법이다. 다음 줄에는 각 문자가 문자열에 나타나는 횟수를 뜻하는 $N$개의 정수 $C_i$ ($0 \le C_i \le 100\,000$)가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄에 하나씩, 주어진 문자열의 가능한 최소 $K$진법 인코딩 길이를 출력한다.

두 테스트 케이스 모두 다음과 같이 배정하면 최소 길이를 얻을 수 있다.

첫 번째 케이스는 $3 + 4 + 3 = 10$ 길이로 문자열을 표현할 수 있다. 두 번째 케이스는 $3 + 4 + 2 = 9$ 길이로 표현할 수 있다.