CF1389B.Array Walk

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 \lt 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 \gt 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?

给你一个由 $n$ 个正整数组成的数组 $a_1, a_2, \dots, a_n$。

初始时你位于下标 $1$，当前得分为 $a_1$。你可以执行以下两种操作：

1. 向右移动：从当前下标 $x$ 移动到 $x+1$，并将 $a_{x+1}$ 加入你的得分。该操作仅当 $x \lt n$ 时允许执行。
2. 向左移动：从当前下标 $x$ 移动到 $x-1$，并将 $a_{x-1}$ 加入你的得分。该操作仅当 $x \gt 1$ 时允许执行；此外，你不能连续执行两次或更多次向左移动。

你需要恰好执行 $k$ 次移动，且其中向左移动的次数至多为 $z$ 次。

你所能获得的最高得分是多少？

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含三个整数 $n, k$ 和 $z$（$2 \le n \le 10^5$，$1 \le k \le n - 1$，$0 \le z \le \min(5, k)$）——分别表示数组中的元素个数、你需要执行的总步数，以及你最多可以向左移动的步数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^4$）——给定的数组。

所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

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.

输出 $t$ 个整数——对每个测试用例，输出在总共恰好进行 $k$ 次移动、其中向左移动的次数不超过 $z$ 次、且不存在连续两次或更多次向左移动的前提下，所能获得的最大得分。

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

在第一个测试用例中，你完全不允许向左移动。因此，你需要向右移动四次，得到的分数为 $a_1 + a_2 + a_3 + a_4 + a_5$。

在第二个示例中，你可以向左移动一次。因此，可以按如下顺序移动：右、右、左、右。所得分数为 $a_1 + a_2 + a_3 + a_2 + a_3$。

在第三个示例中，你最多可向左移动四次，但这样做并非最优；你只需向右移动四次，即可获得分数 $a_1 + a_2 + a_3 + a_4 + a_5$。