아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

근무 중 수면

시간 제한1초메모리 제한256 MB

요약
N분 가운데 정확히 M분을 R분 이하로 끊어 자면서 연속 수면의 k번째 분 기운을 k배로 더한 합이 가장 커지도록 구합니다.
난이도

보통10점 중 6점

유형
동적 계획법
정답자
아직 제출이 없습니다

문제

회사에서 근무하는 중인데, 퇴근하자마자 프로그래밍 대회가 열린다. 좋은 성적을 내려면 근무 시간에 잠을 자서 체력을 최대한 회복해야 한다.

근무 시간은 NN분이고, 0≤i<N0 \le i < N인 ii에 대해 ii번 분의 회복량은 eie_i다. 자야 하는 시간은 정확히 MM분이다. 다만 한 번에 RR분을 넘겨 자면 상사가 알아채므로, 이어서 자는 구간의 길이는 최대 RR분이다. 서로 다른 두 수면 구간 사이에는 깨어 있는 분이 적어도 하나 있다. 두 구간이 붙어 있으면 하나의 긴 구간이다.

이어서 자면 보너스가 붙는다. 한 구간에서 kk번째로 자는 분은 회복량이 kk배가 된다. 예를 들어 회복량이 10,10,910, 10, 9인 세 분을 이어서 자면 10+2×10+3×9=5710 + 2 \times 10 + 3 \times 9 = 57만큼 회복한다.

MM분을 다 자면 완전히 회복되어 그날은 더 잘 수 없다. 잠은 시계의 분이 바뀌는 순간에만 시작하고 끝낼 수 있다.

하루 동안 회복할 수 있는 체력의 최댓값을 구하는 프로그램을 작성하라.

입력

첫 줄에 테스트 케이스의 개수 TT가 주어진다.

각 테스트 케이스의 첫 줄에는 근무 시간 NN, 자야 하는 시간 MM, 한 번에 이어서 잘 수 있는 최대 시간 RR이 공백으로 구분되어 주어진다. 둘째 줄에는 NN개의 정수 e0,e1,…,eN−1e_0, e_1, \dots, e_{N-1}이 공백으로 구분되어 주어진다.

  • 0<T≤1000 < T \le 100
  • 0<N≤5000 < N \le 500
  • 0<M≤500 < M \le 50
  • 0<R≤500 < R \le 50
  • 0≤ei≤1000 \le e_i \le 100

출력

각 테스트 케이스마다 한 줄에, 정확히 MM분을 자서 얻을 수 있는 회복량의 최댓값을 출력한다. MM분을 자는 것이 불가능하면 impossible을 출력한다.

예제2

  1. 예제 1

    입력
    2
10 3 3
10 10 9 6 5 4 2 1 4 4
10 6 1
1 2 3 4 5 6 7 8 9 10
    예상 출력
    57
impossible

  2. 예제 2

    입력
    3
4 2 2
10 0 0 9
5 3 1
1 2 3 4 5
1 1 1
0
    예상 출력
    19
9
0