문자 입력 분노 (small)

문제

친구인 루니 교수가 얼굴이 붉어진 채 연구실로 들어왔다. 첫마디는 이랬다. "휴대폰 만드는 사람들 정말 못 참겠어. 한 줄짜리 문자를 보내려는데 입력하는 데만 십 분이 넘게 걸렸다니까." 나는 그를 달래려 했다. "무슨 일인데요? 왜 그렇게 오래 걸렸어요?" 교수는 말을 이었다. "안 보이나? 글자 배치가 완전히 엉망이잖아. 's'가 왜 그 키의 네 번째 글자야? 'e'는 왜 자기 키의 첫 글자가 아니고? 's' 하나 쓰려고 '7'을 네 번 눌러야 한다니. 제정신이 아니야!"

"진정하세요." 내가 말했다. "이 방식은 문자 메시지가 생기기 훨씬 전부터 쓰던 거예요. 그대로 둬야 했던 거죠."

"그건 변명이야." 교수의 얼굴은 점점 더 붉어졌다. "이제 다 바꿀 때가 됐어. 애초에 어리석은 생각이었고. 그리고 말인데, 왜 글자를 키 여덟 개에만 올려놨지? 열두 개를 다 쓰면 안 되나? 왜 꼭 연속이어야 하고?"

"음... 저는... 잘... 모르겠네요." 내가 답했다.

"됐어. 저 사람들은 무능한 게 분명해. 누군가는 더 나은 방식을 내놓을 수 있을 거야."

교수는 그런 부류였다. 문제를 두고 불평은 하면서 직접 풀어 보지는 않는 사람.

이 문제에서는 메시지를 입력하는 데 필요한 키 누름 횟수를 최소로 만드는 글자 배치를 찾는다. 키의 개수, 한 키에 올릴 수 있는 글자의 최대 개수, 알파벳의 전체 글자 수, 그리고 메시지에서 각 글자가 쓰인 빈도가 주어진다. 글자는 어느 키에든, 어떤 순서로든 놓을 수 있다. 각 글자는 한 키에만 나타난다. 알파벳의 글자 수가 26개보다 많을 수도 있다(영어가 아니다).

참고로 지금 쓰이는 휴대폰 자판은 다음과 같다.

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이다.

입력

첫 줄에 테스트 케이스의 수 $N$ 이 주어진다. 이어서 $N$ 개의 케이스가 주어지고, 각 케이스는 두 줄이다.

케이스의 첫 줄에는 한 키에 올릴 수 있는 글자의 최대 개수 $P$ , 쓸 수 있는 키의 개수 $K$ , 알파벳의 글자 수 $L$ 이 공백 하나로 구분되어 주어진다. 둘째 줄에는 음이 아닌 정수 $L$ 개가 주어진다. 각 수는 해당 글자의 빈도다. 첫 번째 수는 첫 번째 글자가 쓰인 횟수, 두 번째 수는 두 번째 글자가 쓰인 횟수이며, 나머지도 같은 순서다.

제한

$P \times K \ge L$
각 글자의 빈도는 0 이상 1,000,000 이하다
$1 \le N \le 10$
$1 \le P \le 10$
$1 \le K \le 12$
$1 \le L \le 100$

출력

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

Case #x: y

$x$ 는 1부터 시작하는 케이스 번호이고, $y$ 는 최적 배치로 메시지를 입력할 때 필요한 키 누름 횟수의 최솟값이다.