给定一个数组 $$$a_1, a_2, \dots, a_n$$$,由 $$$n$$$ 正整数组成。
最初,您站在索引 $$$1$$$ 处,得分等于 $$$a_1$$$。您可以执行两种动作:
1. 向右移动 — 从当前索引 $$$x$$$ 到 $$$x+1$$$ 并将 $$$a_{x+1}$$$ 添加到您的分数中。仅当 $$$x<n$$$ 时才能执行此移动。
2. 向左移动 — 从当前索引 $$$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$$$,并且连续向左移动的次数不超过 $$$z$$$,则您可以获得的最高分数。
示例
输入 #1
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
输出 #1
15 19 150 56
注意
在第一个测试用例中,您根本不允许向左移动。因此,您向右移动四步并获得分数 $$$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$$$。