테마파크

롤러코스터는 정말 재미있다! 테마파크를 방문하는 모든 사람이 롤러코스터를 타고 싶어 하는 것 같다. 어떤 사람들은 혼자 오고, 다른 사람들은 그룹으로 오며, 그룹 전원이 함께 탈 수 없다면 롤러코스터에 탑승하려 하지 않는다. 그리고 롤러코스터를 탄 모든 사람은 다시 타고 싶어 한다. 탑승 요금은 한 사람당 1유로이다. 오늘 롤러코스터가 얼마를 벌지 구하는 것이 여러분의 임무이다.

롤러코스터에는 한 번에 k명이 탈 수 있다. 사람들은 그룹 단위로 줄을 선다. 남은 그룹이 없거나 다음 그룹이 탈 자리가 없을 때까지 그룹들이 한 번에 하나씩 롤러코스터에 탑승한다. 그러면 롤러코스터는 만원이든 아니든 출발한다. 탑승이 끝나면 승객 전원이 같은 순서로 다시 줄을 선다. 롤러코스터는 하루에 R번 운행한다.

예를 들어 R=4, k=6이고 사람들의 그룹이 네 개이며 그 크기가 1, 4, 2, 1이라고 하자. 롤러코스터가 처음 출발할 때는 첫 두 그룹 $[1, 4]$이 탑승하고 좌석 하나가 비게 된다(2명인 그룹은 탈 수 없고, 1명인 그룹은 그들을 앞질러 갈 수 없다). 그러고 나서 이들은 줄의 맨 뒤로 가며, 이제 줄은 2, 1, 1, 4과 같은 모습이 된다. 두 번째에는 롤러코스터에 4명이 탑승한다: $[2, 1, 1]$. 이제 줄은 4, 2, 1, 1과 같은 모습이다. 세 번째에는 6명이 탑승한다: $[4, 2]$. 이제 줄은 $[1, 1, 4, 2]$과 같은 모습이다. 마지막으로 6명이 탑승한다: $[1, 1, 4]$. 롤러코스터는 총 21유로를 벌었다!

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 50. $g_{i}$ ≤ k.

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ R ≤ 1000. 1 ≤ k ≤ 100. 1 ≤ N ≤ 10. 1 ≤ $g_{i}$ ≤ 10.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ R ≤ $10^{8}$. 1 ≤ k ≤ $10^{9}$. 1 ≤ N ≤ 1000. 1 ≤ $g_{i}$ ≤ $10^{7}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 공백으로 구분된 세 정수 R, k, N이 주어진다. 둘째 줄에는 공백으로 구분된 N개의 정수 $g_{i}$이 주어지며, 각각은 탑승하려는 그룹의 크기이다. $g_{0}$은 첫 번째 그룹의 크기이고, $g_{1}$은 두 번째 그룹의 크기이며, 이후도 같은 방식이다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 롤러코스터가 번 유로의 액수이다.