保龄球

题目描述:

保龄球这项运动很流行，主要原因在于这项运动能够保住年龄永驻青春。现在一排排了很多球瓶，每个球瓶上面有一个数字，表示击中它的得分。给你一定数量的保龄球。

    例如，一排球瓶如下：

    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

提示:

单调队列优化

时间限制: 1000ms
空间限制: 256MB

---