数组漫步

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个由 $n$ 个正整数组成的数组 $a_1,a_2,\ldots,a_n$。你最初位于下标 $1$，初始得分为 $a_1$。

你需要恰好移动 $k$ 次。每次可以向右或向左移动一格，并把到达位置的数组元素加入得分。向左移动的总次数不能超过 $z$，且不能连续两次向左移动。所有移动都必须停留在数组范围内。

求能够获得的最大得分。

输入格式

第一行包含一个整数 $t$，表示测试组数。

每组数据的第一行包含三个整数 $n,k,z$；第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组数据输出一行一个整数，表示最大得分。

样例输入 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

数据范围

对于所有数据，$1\le t\le10^4$，$2\le n\le10^5$，$1\le k\le n-1$，$0\le z\le\min(5,k)$，$1\le a_i\le10^4$，且单个输入文件内所有测试组的 $n$ 之和不超过 $3\cdot10^5$。