题目描述

今天 $HGNU$ 小学的信息技术王老师开展了信息技术期末考试，他出的卷子一共有 $n$ 道题。王老师班上的小聂拿到试卷后，觉得题目过于简单，因此并不打算把所有题全部做完。为了寻找乐趣，他想选 $2$ 个长度为 $k$ 且不重合的区间（即 $[L,L+1,L+2,....,L+k-1], [R,R+1,R+2,...,R+k-1], R \ge L+k$），只做这 $2k$ 道题，并且想保证他获得的分数尽可能大。

输入格式

第一行输入一个整数 $t(1 \le t \le 10)$，表示接下来要解决 $t$ 组测试用例。对于每组测试用例，第一行输入两个整数 $n(2 \le n \le 200000), k(1 \le k, 2k \le n)$，第二行一个长度为 $n$ 的数组 $grade(-100000 \le grade[i] \le 100000)$，$grade[i]$ 表示第 $i$ 题的分数。

输出格式

对于每组测试用例，都输出一行，为小聂能获得的最大分数。

样例

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

6
7