sohyunzzq   1년 전

문제

오늘 매우 바쁜 일정이 있으며, 중요한 일들로 가득 차 있다. 모든 활동이 겹치지 않도록 준비에 최선을 다했다. 이제 아침이고, 당신은 모든 열정을 쏟아붓는다 하더라도 이 모든 일을 전력으로 해낼 수 없을까 봐 걱정된다.

에너지를 신중하게 관리해야 한다. 하루를 시작할 때는 E 줄의 에너지를 가진다. 에너지가 0 줄 밑으로 떨어지면 탈진하게 된다. 각 활동에 대해 0 이상의 정수 에너지를 사용할 수 있다 (게으르다면 0을 쓸 수도 있다). 그리고 각 활동이 끝난 후에는 R 줄의 에너지를 회복한다. 아무리 게으르더라도 에너지는 최대 E 줄을 넘을 수 없다; 즉, 그 이상 회복되는 에너지는 버려진다.

이제 어떤 활동들 (예: Code Jam 문제 풀이)은 다른 활동보다 더 중요하다. i 번째 활동은 vi의 값을 가지며, 이는 이 활동이 당신에게 얼마나 중요한지를 나타낸다. 각 활동에서 얻는 **이익(gain)**은 활동에 소비한 에너지와 해당 활동의 가치 vi를 곱한 값이다. 당신은 총 이익을 최대화하기 위해 에너지를 효율적으로 관리하고자 한다.

일정은 변경할 수 없으며, 주어진 순서대로 활동을 해야 한다. 주어진 일정 안에서 최선을 다해 에너지를 관리해야 한다.

입력

입력의 첫 줄은 테스트 케이스의 개수 T이다. 그 후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

첫 줄에는 세 개의 정수 E (최대 및 초기 에너지), R (각 활동 후 회복되는 에너지), N (오늘 계획된 활동 수)가 주어진다.
두 번째 줄에는 N개의 정수 vi가 주어지며, 각각의 활동에 대한 가치이다.

제한사항:

  • 1 ≤ T ≤ 100

  • 1 ≤ E ≤ 5

  • 1 ≤ R ≤ 5

  • 1 ≤ N ≤ 10

  • 1 ≤ vi ≤ 10

출력

각 테스트 케이스마다 "Case #x: y" 형태로 출력하시오. 여기서 x는 테스트 케이스 번호(1부터 시작), y는 그 날 에너지 관리를 통해 얻을 수 있는 최대 이익이다.

댓글을 작성하려면 로그인해야 합니다.