문자 입력 타수 최소화

휴대폰 키패드는 키 하나에 여러 글자를 몰아 놓고, 키를 누른 횟수로 글자를 구분한다. 첫 번째 누름은 그 키의 첫 글자를 입력하고, 이후의 누름은 그 키의 다음 글자로 한 칸씩 넘어간다.

지금 쓰이는 배치는 이렇다.

key 2: abc
key 3: def
key 4: ghi
key 5: jkl
key 6: mno
key 7: pqrs
key 8: tuv
key 9: wxyz

이 배치로 "snow"를 입력하려면 7을 네 번, 6을 두 번, 6을 세 번, 9를 한 번 눌러야 하므로 타수는 모두 10이다. s가 7번 키의 네 번째 글자라서 네 번을 눌러야 하고, 자주 쓰는 글자가 뒤쪽에 놓이면 타수가 이렇게 불어난다.

배치를 처음부터 다시 정하자. 키 하나에 놓을 수 있는 글자 수의 상한 $P$, 쓸 수 있는 키의 개수 $K$, 알파벳의 글자 수 $L$, 그리고 메시지에서 각 글자가 쓰인 횟수가 주어진다. 알파벳 순서와 관계없이 어느 글자든 어느 키의 어느 자리에나 놓을 수 있고, 한 글자는 정확히 한 키에만 놓는다. 알파벳은 26자보다 많을 수도 있다.

메시지 전체를 입력하는 데 드는 타수의 최솟값을 구하라.

첫 줄에 테스트 케이스의 수 $N$이 주어진다. 이어서 케이스가 $N$개 주어진다. 각 케이스는 두 줄이다. 첫 줄에는 키 하나에 놓을 수 있는 글자 수의 상한 $P$, 키의 개수 $K$, 알파벳의 글자 수 $L$이 공백 하나로 구분되어 주어진다. 둘째 줄에는 음이 아닌 정수 $L$개가 주어지며, $i$번째 수는 $i$번째 글자가 메시지에서 쓰인 횟수다.

제한

• $P \times K \ge L$
• $1 \le N \le 100$
• $1 \le P \le 1\,000$
• $1 \le K \le 1\,000$
• $1 \le L \le 1\,000$
• 각 글자가 쓰인 횟수는 $0$ 이상 $1\,000\,000$ 이하

케이스마다 한 줄씩 다음 형식으로 출력한다.

Case #x: y

$x$는 $1$부터 시작하는 케이스 번호이고, $y$는 최적 배치로 메시지를 입력할 때 드는 최소 타수다.