cho.sh

에너지 관리

상한이 있고 매 활동 후에 충전되는 에너지를 정해진 순서의 활동에 나누어 가치에 가중된 이득을 최대화합니다.

보통5그리디시뮬레이션면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB

문제

오늘 일정은 중요한 일로 빽빽하다. 일정이 서로 겹치지 않도록 미리 잘 맞춰 두었다. 이제 아침이 되었는데, 의욕과 달리 이 모든 일을 온전히 해낼 체력이 남아 있을지 걱정된다.

에너지를 아껴 써야 한다. 하루를 시작할 때 에너지는 최대치인 EE 줄(joule)이다. 에너지가 0 미만으로 내려가면 탈진하므로 그렇게 쓸 수는 없다. 각 활동에는 0 이상의 정수 줄만큼 에너지를 쓸 수 있고, 귀찮으면 0을 써도 된다. 활동을 하나 마칠 때마다 에너지 RR 줄을 회복한다. 다만 아무리 게으르게 굴어도 에너지는 어느 순간에도 EE 줄을 넘지 못한다. 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≤1071 \le E \le 10^7
  • 1≤R≤1071 \le R \le 10^7
  • 1≤N≤1041 \le N \le 10^4
  • 1≤vi≤1071 \le v_i \le 10^7

출력

각 테스트 케이스마다 한 줄에 Case #x: y 형식으로 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 그날 에너지를 가장 잘 배분했을 때 얻는 이득의 최댓값이다. 답은 64비트 정수 범위에 들어간다.

힌트

예제의 첫 번째 케이스에서는 첫 활동에 에너지 5를 모두 써서 이득 10을 얻고, 2를 회복해 두 번째 활동에 쓴다. 두 번째 케이스에서는 첫 활동에 2만 쓰고 그 2를 회복한 뒤 두 번째 활동에 5를 쓴다. 세 번째 케이스에서는 회복량이 최대치와 같아서 활동을 마칠 때마다 에너지가 항상 가득 차므로, 활동마다 3을 전부 쓸 수 있다.