• # For Solution

You are given an array AA of NN elements. You can do the following operations on that array:

• Remove the leftmost element of the array, with index ll, for the cost AlAl. This can be done any number of times if the array is non-empty (has at least 11 element).
• Remove the rightmost element of the array, with index rr, for the cost ArAr. This can be done any number of times if the array is non-empty (has at least 11 element).
• Remove both the leftmost and rightmost element, with indexes ll and rr respectively, for a fixed cost XX which is given. This operation can only be done KK times and only if the array has at least 22 elements left. Clear the Array solution codechef

If the array has only 11 element left, then the rightmost element is the same as the leftmost element so the first and second operations will have the same cost.

You have to print the minimum cost to clear the array (remove all elements using one of the three operations above).

NOTE: The answer may not fit in 32-bit integers, so please use 64-bit data types in your programming language.

### Input Format

• The first line of the input contains TT – the number of test cases. Then the test cases follow.

• Each test case contains 2 lines of input.

• The first line of each test case contains three integers: NNKK, and XX separated by spaces.

• The second line of each test case contains NN space-separated positive integers, A1,A2,ANA1,A2,…AN.

### Output Format Clear the Array solution codechef

For each test case, output on one line the minimum cost to clear the array.

### Constraints

• 1T2001≤T≤200
• 1N50001≤N≤5000
• 0KN20≤K≤⌊N2⌋
• 1X1091≤X≤109
• 1Ai1091≤Ai≤109

### Sample Input 1

3
5 2 7
9 10 11 12 13
5 0 7
9 9 9 9 9
5 2 7
9 1 2 3 10


### Sample Output 1  Clear the Array solution codechef

23
45
13


### Explanation

For the first test case, we can remove A1A1 for cost 99, which makes the array [10,11,12,13][10,11,12,13]. Then we can do the third operation to remove 1010 and 1313 for cost 77, which makes the array [11,12][11,12]. We can again do the third operation to remove 1111 and 1212 for cost 77 which clears the array.

The total cost is therefore 2323, which is the minimum cost possible.