에너지 관리

오늘 당신의 일정은 해야 할 중요한 일들로 가득 차 매우 바쁘다. 당신은 모든 활동이 서로 겹치지 않도록 열심히 준비했다. 이제 아침이 되었고, 열정이 넘치더라도 이 모든 일에 온전히 몰입할 만큼의 에너지가 없을까 봐 걱정하고 있다.

에너지를 신중하게 관리해야 한다. 하루를 에너지로 가득 찬 상태, 정확히는 E줄의 에너지를 가진 상태로 시작한다. 에너지가 0줄 미만이 되면 탈진해 쓰러지므로 그렇게 할 수 없다. 각 활동에 음이 아닌 정수 줄만큼의 에너지를 사용할 수 있으며(게으른 기분이라면 0을 사용해도 된다), 각 활동이 끝난 뒤에는 에너지를 R줄 회복한다. 하지만 아무리 게으르더라도 어느 때든 E줄보다 많은 에너지를 가질 수는 없다. 그 한도를 넘어 회복하게 되는 추가 에너지는 모두 낭비된다.

어떤 일들은(Code Jam 문제를 푸는 것처럼) 다른 일들보다 더 중요하다. i번째 활동에는 그 활동이 자신에게 얼마나 중요한지를 나타내는 값 $v_{i}$가 있다. 각 활동에서 얻는 이득은 그 활동의 값에 해당 활동에 사용한 에너지의 양(줄 단위)을 곱한 값이다. 총이득이 가능한 한 커지도록 에너지를 관리하고자 한다.

달력에 있는 활동들의 순서를 바꿀 수 없다는 점에 유의한다. 주어진 일정에 맞춰 에너지를 최대한 잘 관리해야 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100.

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

1 ≤ E ≤ 5. 1 ≤ R ≤ 5. 1 ≤ N ≤ 10. 1 ≤ $v_{i}$ ≤ 10.

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

1 ≤ E ≤ $10^{7}$. 1 ≤ R ≤ $10^{7}$. 1 ≤ N ≤ $10^{4}$. 1 ≤ $v_{i}$ ≤ $10^{7}$.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 설명된다. 첫째 줄에는 세 정수, 즉 에너지의 최대량이자 초기량인 E, 각 활동 후 회복하는 양인 R, 하루 동안 계획된 활동의 수인 N이 주어진다. 둘째 줄에는 오늘 계획한 활동들의 값을 나타내는 N개의 정수 $v_{i}$가 주어진다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작한다), y는 그날 에너지를 관리하여 얻을 수 있는 최대 이득이다.

첫 번째 케이스에서는 에너지 5줄을 모두 첫 번째 활동에 사용하여 이득 10을 얻고, 2을 회복하여 두 번째 활동에 사용할 수 있다. 두 번째 케이스에서는 첫 번째 활동에 2줄을 사용하고, 그만큼 회복한 뒤 두 번째 활동에 5을 사용한다. 세 번째 케이스에서는 회복량이 최대 에너지와 같으므로 각 활동 후에 항상 모든 에너지를 회복한다. 따라서 각 활동에 3줄을 전부 사용할 수 있다.