Array Walk
Contest: Educational Codeforces Round 92 (Rated for Div. 2)
Difficulty rating: 1600
Tags: brute force, dp, greedy

You are given an array $$$a_1, a_2, \dots, a_n$$$, consisting of $$$n$$$ positive integers.

Initially you are standing at index $$$1$$$ and have a score equal to $$$a_1$$$. You can perform two kinds of moves:

1. move right — go from your current index $$$x$$$ to $$$x+1$$$ and add $$$a_{x+1}$$$ to your score. This move can only be performed if $$$x<n$$$.
2. move left — go from your current index $$$x$$$ to $$$x-1$$$ and add $$$a_{x-1}$$$ to your score. This move can only be performed if $$$x>1$$$. Also, you can't perform two or more moves to the left in a row.

You want to perform exactly $$$k$$$ moves. Also, there should be no more than $$$z$$$ moves to the left among them.

What is the maximum score you can achieve?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains three integers $$$n, k$$$ and $$$z$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n - 1$$$, $$$0 \le z \le min(5, k)$$$) — the number of elements in the array, the total number of moves you should perform and the maximum number of moves to the left you can perform.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$) — the given array.

The sum of $$$n$$$ over all testcases does not exceed $$$3 \cdot 10^5$$$.

Output format:
Print $$$t$$$ integers — for each testcase output the maximum score you can achieve if you make exactly $$$k$$$ moves in total, no more than $$$z$$$ of them are to the left and there are no two or more moves to the left in a row.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase you are not allowed to move left at all. So you make four moves to the right and obtain the score $$$a_1 + a_2 + a_3 + a_4 + a_5$$$.

In the second example you can move one time to the left. So we can follow these moves: right, right, left, right. The score will be $$$a_1 + a_2 + a_3 + a_2 + a_3$$$.

In the third example you can move four times to the left but it's not optimal anyway, you can just move four times to the right and obtain the score $$$a_1 + a_2 + a_3 + a_4 + a_5$$$.

Example input:
4
5 4 0
1 5 4 3 2
5 4 1
1 5 4 3 2
5 4 4
10 20 30 40 50
10 7 3
4 6 8 2 9 9 7 4 10 9

Example output:
15
19
150
56

Editorial:
Notice that your final position is determined by the number of moves to the left you make. Let there be exactly $$$t$$$ moves to the left, that leaves us with $$$k - t$$$ moves to the right. However, let's interpret this the other way. You have $$$t$$$ pairs of moves (right, left) to insert somewhere inside the sequence of $$$k - 2t$$$ moves to the right.
Easy to see that all the positions from $$$1$$$ to $$$k - 2t + 1$$$ will always be visited. And the extra pairs can also increase the score by visiting some positions ($$$i+1$$$, $$$i$$$) for some $$$i$$$ from $$$1$$$ to $$$k - 2t + 1$$$.
Notice that it's always optimal to choose exactly the same $$$i$$$ for all the pairs (right, left). And that $$$i$$$ should be such that $$$a_{i+1} + a_i$$$ is maximum possible.
You can implement this idea in a straightforward manner: iterate over $$$t$$$ and calculate the sum of values from $$$1$$$ to $$$k - 2t + 1$$$ and the maximum value of $$$a_{i+1} + a_i$$$ over $$$i$$$ from $$$1$$$ to $$$k - 2t + 1$$$.
That will lead to a $$$O(zn)$$$ solution per testcase.
You can optimize it to $$$O(n)$$$ with prefix sums or with some clever order to iterate over $$$t$$$. It's also possible to iterate over the final position and restore the number of left moves required to achieve it.
Overall complexity: $$$O(zn)$$$ or $$$O(n)$$$ per testcase.