Lady Layton and Stone Game

Problem Description

Katori has many piles of stones, where there are $a_i$ piles containing exactly $i$ stones for $i = 1, 2, \ldots, n$. Now, she wants to collect all these piles into one pile by merging one or more times. Each time she can pick $k$ $(L \leq k \leq R)$ piles and merge them into one, and the cost of that will be the number of stones in the new pile. Can you help her find the best way to achieve that with the minimum possible total cost?

Input

There are several test cases. The first line contains an integer $T$ $(1 \leq T \leq 10)$, denoting the number of test cases. Then follow all the test cases. For each test case, the first line contains three integers $n$, $L$ and $R$ $(1 \leq n \leq 10^5, 2 \leq L \leq R \leq \sum_{i = 1}^{n}{a_i})$, denoting the maximum number of stones in each piles at the beginning, the lower bound and the upper bound of the number of piles she can merge at once, respectively. The second line contains $n$ integers, where the $i$-th integer is $a_i$ $(1 \leq a_i \leq 10^5)$, the number of piles containing exactly $i$ stones at the beginning.

Output

For each test case, output in one line $-1$ if it is impossible for her to achieve the task, or otherwise the minimum total cost to finish that.

Sample Input

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

Sample Output

2
9
6
-1

Hint

For the first sample case, there are two piles [1, 1] at the beginning. The best way is to merge [1, 1] into [2] directly, and the cost is 2. For the second sample case, there are three piles [1, 2, 3] at the beginning. The best way is to merge [1, 2] into [3] at first, and then merge [3, 3] into [6]. The minimum total cost is 3 + 6 = 9. For the third sample case, there are three piles [1, 2, 3] at the beginning. The best way is to merge [1, 2, 3] into [6] directly, and the cost is 6. For the fourth sample case, there are four piles [1, 2, 3, 4] at the beginning. Neither can she collect them into one pile directly nor by merging several times, so it is impossible for her to achieve the task.

Source

2020 Multi-University Training Contest 3