P4481 [BJWC2018] Sequence Merging

On a verdant day, Scape went to the XX division to be crowned king.

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.

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$.

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

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