B. 数组行走

每个测试的时间限制：$2$ 秒
内存限制：$256$ 兆字节

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

初始时你站在下标 $1$ 处，分数等于 $a_1$。你可以执行两种移动：

• 向右移动：从当前下标 $x$ 移动到 $x+1$，并将 $a_{x+1}$ 加到你的分数上。仅当 $x < n$ 时可执行。
• 向左移动：从当前下标 $x$ 移动到 $x-1$，并将 $a_{x-1}$ 加到你的分数上。仅当 $x > 1$ 时可执行。
  注意：你不能连续执行两次或更多次向左移动。

你想恰好执行 $k$ 次移动，并且其中向左移动的次数不超过 $z$。

请问你能获得的最大分数是多少？

输入
第一行包含一个整数 $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$。

输出
输出 $t$ 个整数 —— 对于每个测试用例，输出在恰好执行 $k$ 次移动、向左移动次数不超过 $z$ 且没有连续两次向左移动的条件下，能获得的最大分数。

示例

输入

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

输出

15
19
150
56

说明

• 第一个测试用例：不允许向左移动，因此执行 $4$ 次向右移动，得分为 $a_1 + a_2 + a_3 + a_4 + a_5 = 15$。
• 第二个测试用例：可以向左移动一次。可以按照 右、右、左、右 的顺序移动，得分为 $a_1 + a_2 + a_3 + a_2 + a_3 = 19$。
• 第三个测试用例：最多允许向左移动 $4$ 次，但最优方案仍是 $4$ 次向右移动，得分为 $a_1 + a_2 + a_3 + a_4 + a_5 = 150$。