28340번 - K-ary Huffman Encoding

문제

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

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

1. $N$개의 각 문자에 $K$진법 문자열을 하나씩 배정해야 한다.
2. 배정된 $K$진법 문자열들이 서로의 접두사 (prefix)일 수 없다.

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

4ドル$개의 문자 각각에 서로의 접두사가 아닌 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ドル ≤ N ≤ 10,000円$), $K$ (2ドル ≤ K ≤ 10,000円$)가 공백으로 구분되어 주어진다. $N$은 Huffman 나라의 문자의 수이고 $K$는 인코딩할 진법을 나타낸다. 다음 줄에는 각 문자가 문자열에 몇 번이나 나타나는지를 의미하는 $N$개의 정수 $C_i$ (0ドル ≤ C_i ≤ 100,000円$)가 공백으로 구분되어 주어진다.

출력

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

제한

힌트

두 테스트 케이스 모두

로 할당하면 최소의 길이를 얻을 수 있다. 첫 번째 케이스의 경우 3ドル + 4 + 3 = 10$ 길이로 문자열을 표현할 수 있으며, 두 번째 케이스의 경우 3ドル + 4 + 2 = 9$ 길이로 문자열을 표현할 수 있다.