cho.sh

체력 관리 (Small)

순서가 정해진 활동을 하며 매번 R만큼 E 한도까지 에너지를 회복하면서 활동 가치와 사용 에너지의 곱의 합이 최대가 되도록 에너지를 배분합니다.

보통4동적 계획법면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

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

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

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

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

입력

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

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

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤E≤51 \le E \le 5
  • 1≤R≤51 \le R \le 5
  • 1≤N≤101 \le N \le 10
  • 1≤vi≤101 \le v_i \le 10

출력

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

힌트

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