1537: Red

    商场正在进行一个游戏。游戏的规则是这样子的：一个铺在地上的长条，每个格子里面写着数字。顾客刚开始从起点出发，每次可以往前跳若干个格子，接着如果落脚的格子是正数，那么得到这么多钱，如果是负数，那么意味着你要付出这么多钱。每回合往前跳的步数有限制，并且你要在规定的步数之内跳到终点，否则将会遭受更大的惩罚。

    举个例子，如下图，假设我们要在5回合之内完成游戏，并且每回合我们往前跳的格子数为1到4。注意我们是正好在第一格之前的位置开始，所以如果第一回合我们跳一格，那么就到达了第一格格子。同时注意我们必须到达终点。当然不必正好到达，只要超过最后一格即可。

上图展示了两种不同的游戏策略。如果5回合，我们按照2,3,4,1,1的方式跳，那么就得到50+30+20+70=170元；当然，最优策略可以得到220元，像上面第二条线路一样。

    输入数据的第一行包含一个正整数t（t ≤ 20），代表测试数据的组数。

    对于每组测试数据，第一行包含三个整数N，S，T，N是总的格子的数目，2 ≤ N ≤ 200,S是每回合你最多跳的格子的数目，2 ≤ S ≤ 10，T是最大允许的回合数，N+1 ≤ ST并且T ≤ N+1。接下来一行或者多行，共n个数，代表每个格子上写的数，绝对值不超过10000。

    对于每组数据，输出一行一个整数，代表可能的最大获利。

    当然，数据保证你可以从头走到尾。

2
10 4 5
100 50 -20 60 30
-10 -30 -50 20 70
9 3 4
150 100 -200
-100 -300 -100
-200 100 150

220
-100