테마파크 롤러코스터

놀이공원에서 롤러코스터는 하루 종일 줄이 끊이지 않는다. 혼자 온 사람도 있고, 여럿이 한 팀으로 와서 반드시 같은 회차에 함께 타려는 사람도 있다. 한 번 탄 사람은 모두 다시 줄을 서고, 요금은 1인당 1유로다. 오늘 롤러코스터가 벌어들이는 금액을 구하라.

롤러코스터는 한 번에 최대 $k$명을 태운다. 사람들은 그룹 단위로 줄을 선다. 대기열 맨 앞의 그룹부터 한 그룹씩 태우되, 남은 그룹이 없거나 다음 그룹이 남은 자리에 다 들어가지 못하면 거기서 탑승을 멈추고 자리가 비어 있어도 출발한다. 뒤에 선 작은 그룹이 앞 그룹을 앞질러 타는 일은 없다. 운행이 끝나면 탔던 그룹은 탑승한 순서 그대로 대기열 맨 뒤에 다시 선다. 롤러코스터는 하루에 $R$번 운행한다.

$R = 4$, $k = 6$이고 그룹의 크기가 앞에서부터 1, 4, 2, 1인 경우를 보자. 첫 번째 운행에는 앞의 두 그룹 [1, 4]가 타고 한 자리가 빈다. 2명 그룹은 자리가 모자라고, 그 뒤의 1명 그룹은 앞질러 탈 수 없다. 이제 대기열은 2, 1, 1, 4가 된다. 두 번째 운행에는 [2, 1, 1]이 타서 4명을 태우고, 대기열은 4, 2, 1, 1이 된다. 세 번째 운행에는 [4, 2]가 타서 6명을 태우고, 대기열은 1, 1, 4, 2가 된다. 네 번째 운행에는 [1, 1, 4]가 타서 6명을 태운다. 하루 수입은 모두 21유로다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 각 테스트 케이스가 두 줄씩 주어진다. 첫째 줄에는 공백으로 구분된 세 정수 $R$, $k$, $N$이 주어진다. 둘째 줄에는 공백으로 구분된 $N$개의 정수 $g_0, g_1, \dots, g_{N-1}$이 주어지며, $g_i$는 줄을 선 순서로 $i$번째 그룹의 인원수다.

제한

• $1 \le T \le 50$
• $1 \le R \le 10^8$
• $1 \le k \le 10^9$
• $1 \le N \le 1000$
• $1 \le g_i \le 10^7$
• 모든 $i$에 대해 $g_i \le k$

각 테스트 케이스마다 한 줄에 Case #x: y 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 롤러코스터가 하루 동안 벌어들인 금액이며 단위는 유로다.