You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

为爱冲锋！！！

题目描述

致敬勇士：

最近网传为爱冲锋的勇士，不禁让人对他的遭遇同情，为他做诗一首“赤脚勇士一挑五，为爱狂奔终是苦。世人何必羡梁祝，从来金莲在水浒。”正所谓笑梗不笑人，这才是正确的观念，当你看了这个故事，那么将给你布置这样一个任务，来判断你是否拥有一个正确的玩梗观念。给你一张试卷，一共n道题，每道题，能获得的分数为$a_i$，要求你做的题目数量为$2k$，这个区间的要求是2个不连续的长度为$k$的区间,并且你要将你的分数尽可能的大，即$[l,l+1,l+2,.....,l+k-1],[r,r+1,r+2,...,r+k-1](l+k\leq r)$

输入

第一行一个整数$t(t\leq 10)$,代表有$t$组数据。 接下来一行2个整数$n,k(2\leq n \leq 2*10^5,1\leq k,2k,\leq n)$,代表$n$题，区间长度$k$。 接下$n$个整数$a_1,a_2,....,a_n(-10^5\leq a_i \leq 10^5)$,代表第$i$题的分数为$a_i$。

输出

输出一个整数，代表你能获得的最大分数.

样例

2
6 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1

6
7