놀이공원 (Large)

문제

놀이공원에서 가장 인기 있는 놀이기구는 롤러코스터다. 혼자 오는 사람도 있고 여럿이 무리를 지어 오는 사람도 있는데, 함께 온 그룹은 반드시 다 같이 타려고 한다. 한 번 타 본 사람은 또 타고 싶어 해서, 내린 뒤에도 다시 줄을 선다. 탑승료는 한 번에 한 사람당 1유로다. 오늘 이 롤러코스터가 벌어들일 금액을 예측하라.

롤러코스터에는 한 번에 최대 $k$ 명이 탈 수 있고, 그룹은 줄을 서서 기다린다. 그룹은 줄 순서대로 차례차례 탑승하며, 모든 그룹이 다 타거나 다음 차례 그룹이 통째로 앉을 자리가 남지 않으면 빈자리가 있어도 그대로 출발한다. 뒤에 선 그룹이 앞 그룹을 앞지를 수는 없다. 내린 그룹은 탑승한 순서 그대로 줄 맨 뒤에 다시 선다. 롤러코스터는 하루에 $R$ 번 출발한다.

예를 들어 $R = 4$ , $k = 6$ 이고 1명, 4명, 2명, 1명인 네 그룹이 이 순서로 서 있다고 하자. 첫 번째 출발에는 1명 그룹과 4명 그룹이 타고, 다음 차례인 2명 그룹은 앉을 자리가 모자라므로 한 자리를 비운 채 출발한다. 이들이 줄 뒤에 다시 서면 줄은 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$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어지고, 각 케이스는 두 줄로 이루어진다. 첫 줄에는 공백으로 구분된 세 정수 $R$ , $k$ , $N$ 이 주어진다. 둘째 줄에는 공백으로 구분된 $N$ 개의 정수 $g_i$ 가 주어진다. $g_i$ 는 줄에 서 있는 각 그룹의 인원 수이고, $g_0$ 이 맨 앞 그룹, $g_1$ 이 그다음 그룹이다.

제한

$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$
$g_i \le k$

출력

각 테스트 케이스마다 한 줄씩 Case #X: Y 형식으로 출력한다. $X$ 는 1부터 시작하는 테스트 케이스 번호이고, $Y$ 는 그날 롤러코스터의 매출이다.