题目内容

给定长度为$m$的整数列$b_1,b_2,...b_m$。需要恰好挑出两段非空子段。所谓子段，就是原列里一段连续位置。这两段不许共用任何位置，并且二者之间相隔得大于$g$。比方说，挑[$1,5$]与[$8,10$]在$g=2$时允许，可一旦$g\ge 3$便不允许。

请让这两段里整数加总尽可能大，并给出该最大值。

输入描述

首行读入一个正整数$q$，代表有多少组测试。

每一组测试里，先在一行读入两个整数$m,g$。下一行读入$m$个整数$b_1,b_2,...b_m$。

$1\le m\le 10^5,-10^4\le b_p\le 10^4,0\le g\le m-2,1\le q\le 5$

输出描述

每一组测试都要打印一行整数，即该组的答案。

样例1

输入

3
4 1
-4 -1 -2 -3
5 1
6 -3 2 -4 8
6 0
3 -10 4 5 -1 6

输出

-4
14
17

说明

第一组测试,只能挑[$2,2$]与[$4,4$]，得到$-1+(-3)=-4$。

第二组测试，可以挑[$1,1$]与[$5,5$]，得到$6+8=14$。

第三组测试,可以挑[$1,1$]与[$3,6$]，得到$3+4+5+(-1)+6=17$。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写