题目描述

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

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

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。