최소 비용 접두사 자유 언어

$d$개의 문자 $c_1, c_2, \ldots, c_d$로 이루어진 알파벳을 사용하여 $n$개의 단어로 된 언어를 만들려고 합니다. 이 언어는 접두사 자유(prefix-free)여야 합니다. 즉, 어떤 단어 $s$가 다른 단어 $t$의 접두사가 되는 단어 쌍 $(s, t)$가 존재하지 않아야 합니다.

각 문자 $c_i$에는 사용 비용 $w_i$가 있습니다. 한 단어의 비용은 그 단어를 이루는 문자들의 비용을 모두 더한 값입니다. 예를 들어 $c_1 = a$, $c_2 = b$, $w_1 = 1$, $w_2 = 10$일 때 단어 aba의 비용은 $1 + 10 + 1 = 12$입니다.

한 언어의 비용은 그 언어에 속한 모든 단어의 비용을 더한 값입니다. 예를 들어 언어 ab, bbb, baaa의 비용은 $11 + 30 + 13 = 54$입니다.

정확히 $n$개의 단어를 갖는 접두사 자유 언어 중에서 가능한 최소 총비용을 구하세요.

$n = 1$인 경우, 유일한 단어로 비용이 $0$인 빈 단어를 사용할 수 있습니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $d$가 주어집니다 ($1 \le n \le 200$, $1 \le d \le 200$). 다음 줄에는 $d$개의 음이 아닌 정수 $w_1, w_2, \ldots, w_d$가 주어집니다. 입력은 두 개의 0으로 이루어진 줄로 끝나며, 이 줄은 테스트 케이스가 아닙니다.

각 테스트 케이스마다, 주어진 $d$개의 문자로 만든 $n$개 단어의 접두사 자유 언어가 가질 수 있는 최소 비용을 한 줄에 출력하세요.