1787：保龄球

【题目描述】

一排球瓶，每个球瓶上面有一个数字，表示击中它的得分。给你一定数量的保龄球。例如，一排球瓶如下：

2 8 5 1 9 6 9 3 2

你有$2$个保龄球，每个球可以击中$3$个球瓶宽度的区域，你可以获得的最大得分为$39$分，这两次分别击中$2+8+5=15,9+6+9=24$。

球瓶的数字有的为负数，可以利用“被击倒的球瓶留下的空白位置”或者“原先球瓶左边和右边本来的空白位置”去尽可能地避免这些负分球。例如，这个例子：

2 8 -5 3 5 8 4 8 -6

如果给你$3$个球，每个球可以击中连续$3$个球瓶的区域，那么你可以最多获得$38$分，这三次分别击中：$2+8=10，3+5+8=16，4+8=12$。

【输入】

输入有多组测试数据。

第一行$t(1≤t≤10)$表示测试数据的个数。

每个测试数据第一行$3$个整数$n(1≤n≤10000),k(1≤k≤500),w(1≤w≤100)$,$n$表示球瓶数量，$k$表示球的数量，$w$表示球能击中连续$W$个球瓶的宽度。

接下来$n$行，每行一个整数按顺序表示对应球瓶的分值($-10000≤$分值$≤10000$)。

【输出】

输出最大得分。

【输入样例】

2
9 2 3
2
8
5
1
9
6
9
3
2
9 3 3
2
8
-5
3
5
8
4
8
-6

【输出样例】

39
38

【提示】

【数据规模】

对于20%的数据，$n≤100$。

对于40%的数据，$k≤30$。

对于100%的数据，$1≤n≤10000,1≤k≤500$。