문자 메시지의 분노

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. P * K ≥ L 0 ≤ 각 문자의 빈도 ≤ 1000000

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ 10 1 ≤ P ≤ 10 1 ≤ K ≤ 12 1 ≤ L ≤ 100

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ 100 1 ≤ P ≤ 1 000 1 ≤ K ≤ 1 000 1 ≤ L ≤ 1 000

입력 파일의 첫째 줄에는 테스트 케이스의 수 N이 주어진다. 이어서 N개의 케이스가 주어진다. 각 케이스는 두 줄로 이루어진다. 첫째 줄에는 키 하나에 배치할 수 있는 문자의 최대 개수(P), 사용할 수 있는 키의 수(K), 알파벳의 문자 수(L)가 각각 하나의 공백으로 구분되어 주어진다. 둘째 줄에는 L개의 음이 아닌 정수가 주어진다. 각 수는 특정 문자의 빈도를 나타낸다. 첫 번째 수는 첫 번째 문자가 사용되는 횟수이고, 두 번째 수는 두 번째 문자가 사용되는 횟수이며, 이후도 같은 방식이다.

각 케이스마다 다음을 출력해야 한다.

Case #x: [minimum number of keypad presses]

이는 최적의 배치에서 메시지를 입력하는 데 필요한 키패드 누름 횟수를 나타낸다.