Description

Scape flipped open the problemset and saw this problem:

There is a sequence $A$ and $L, R$. At each step, you may merge $K$ adjacent elements (with $L \le K \le R$). The cost is the sum of those $K$ elements, and the merge produces a new element whose value is that same sum.

Find the minimum cost to merge the entire sequence into one element.

Without thinking, Scape wrote an $\mathcal{O}(n^4)$ brute force, which actually timed out (TLE). As the king of XX, Scape naturally will not bother with such a “trash” problem; please solve it.

Input Format

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

For each test case, the first line contains three integers $n, L, R$, denoting the length of sequence $A$ and the bounds on $K$.

The second line contains $n$ integers, the sequence $A$.

Output Format

For each test case, output one integer — the answer. If it is impossible, output $0$.

3
3 2 2
1 2 3
3 2 3
1 2 3
4 3 3
1 2 3 4

9
6
0

Hint

Constraints:

• For $20\%$ of the testdata, $n \le 20$.
• For $60\%$ of the testdata, $n \le 50$.
• For $100\%$ of the testdata, $1 \le T \le 10$, $n \le 300$, $A_i \le 100$.

Translated by ChatGPT 5