Sleeping at Work

You are at work, and a programming contest starts right after your working hours end. To do well you have to sleep at work and recover as much energy as possible.

Your workday is $N$ minutes long. Minute $i$ has energy value $e_i$ for every $i$ with $0 \le i < N$. You have to sleep for exactly $M$ minutes. Your boss notices if you sleep more than $R$ minutes in a row, so every run of consecutive sleeping minutes has length at most $R$. Two different runs have at least one waking minute between them. Two runs that touch are one longer run.

Sleeping several minutes in a row gives a bonus. The $k$-th minute of a run has its energy value multiplied by $k$. For instance, sleeping three minutes in a row whose energy values are $10, 10, 9$ gains $10 + 2 \times 10 + 3 \times 9 = 57$ energy.

Once you have slept $M$ minutes you are fully rested and cannot sleep any more that day. You can start and stop sleeping only when the minute indicator on the clock changes.

Write a program that computes the largest amount of energy you can gain during the workday.

The first line contains an integer $T$, the number of test cases.

The first line of each test case contains three integers separated by spaces: the workday length $N$, the required sleep $M$, and the largest number of minutes $R$ you can sleep in a row. The second line contains the $N$ integers $e_0, e_1, \dots, e_{N-1}$ separated by spaces.

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

For each test case print one line with the largest amount of energy that can be gained by sleeping exactly $M$ minutes. If sleeping $M$ minutes is impossible, print impossible.