근무 중 수면

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

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

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

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

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

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

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

• $0 < T \le 100$
• $0 < N \le 500$
• $0 < M \le 50$
• $0 < R \le 50$
• $0 \le e_i \le 100$

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