题目描述
今天 HGNU 小学的信息技术王老师开展了信息技术期末考试,他出的卷子一共有 n 道题。王老师班上的小聂拿到试卷后,觉得题目过于简单,因此并不打算把所有题全部做完。为了寻找乐趣,他想选 2 个长度为 k 且不重合的区间(即 [L,L+1,L+2,....,L+k−1],[R,R+1,R+2,...,R+k−1],R≥L+k),只做这 2k 道题,并且想保证他获得的分数尽可能大。
输入格式
第一行输入一个整数 t(1≤t≤10),表示接下来要解决 t 组测试用例。对于每组测试用例,第一行输入两个整数 n(2≤n≤200000),k(1≤k,2k≤n),第二行一个长度为 n 的数组 grade(−100000≤grade[i]≤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