체력 관리 (Small)

오늘 일정표는 중요한 일로 빽빽하다. 미리 준비해서 어떤 활동도 서로 겹치지 않게 배치해 두었다. 그런데 아침이 되고 보니, 의욕과 별개로 이 많은 일을 전부 온 힘을 다해 해낼 체력이 남을지 걱정이다.

체력을 아껴 써야 한다. 하루를 시작할 때 체력은 $E$ 줄(joule)로 가득 차 있다. 체력이 0 미만으로 내려가면 지쳐 쓰러지므로 그렇게 쓸 수는 없다. 각 활동에는 0 이상의 정수만큼 줄 단위로 체력을 쓸 수 있고(게으름을 피우고 싶다면 0을 써도 된다), 활동이 하나 끝날 때마다 체력을 $R$ 줄 회복한다. 아무리 게으름을 피워도 체력이 $E$ 줄을 넘을 수는 없고, 그 위로 회복되는 몫은 그냥 사라진다.

어떤 일은 다른 일보다 더 중요하다. $i$번째 활동에는 그 일이 자신에게 얼마나 중요한지를 나타내는 값 $v_i$가 있다. 한 활동에서 얻는 이득은 그 활동의 값에 그 활동에 쓴 체력(줄)을 곱한 값이다. 이득의 총합이 최대가 되도록 체력을 배분하려고 한다.

일정표의 순서는 바꿀 수 없다. 주어진 순서를 그대로 두고 체력만 잘 나눠 써야 한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

첫 줄에는 세 정수 $E$, $R$, $N$이 주어진다. $E$는 체력의 최댓값이자 하루를 시작할 때의 체력, $R$은 활동 하나가 끝날 때마다 회복하는 양, $N$은 그날 계획한 활동의 수다. 둘째 줄에는 활동의 값 $v_1, v_2, \dots, v_N$이 순서대로 주어진다.

제한

• $1 \le T \le 100$
• $1 \le E \le 5$
• $1 \le R \le 5$
• $1 \le N \le 10$
• $1 \le v_i \le 10$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 그날 체력을 가장 잘 배분했을 때 얻을 수 있는 이득의 최댓값이다.

예제의 첫 번째 케이스에서는 첫 활동에 체력 5줄을 모두 써서 10을 얻고, 2줄을 회복해 두 번째 활동에 쓴다. 두 번째 케이스에서는 첫 활동에 2줄만 쓰고 그만큼 회복한 뒤 두 번째 활동에 5줄을 쓴다. 세 번째 케이스는 회복량이 체력의 최댓값과 같아서 활동이 끝날 때마다 체력이 다시 가득 차므로, 네 활동 모두에 3줄씩 쓸 수 있다.