Type: Default 1000ms 256MiB

为爱冲锋!!!

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.

为爱冲锋!!!

题目描述

致敬勇士: QQ图片20221114105652.jpg QQ图片20221114105840.jpg QQ图片20221114105944.jpg QQ图片20221114110056.jpg

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

输入

第一行一个整数t(t10)t(t\leq 10),代表有tt组数据。 接下来一行2个整数n,k(2n2105,1k,2k,n)n,k(2\leq n \leq 2*10^5,1\leq k,2k,\leq n),代表nn题,区间长度kk。 接下nn个整数a1,a2,....,an(105ai105)a_1,a_2,....,a_n(-10^5\leq a_i \leq 10^5),代表第ii题的分数为aia_i

输出

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

样例

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

2022ACM新生积分赛 Round #6

Attended
Status
Done (Attended)
Rule
ACM/ICPC
Problem
10
Start at
2022-11-20 13:00
End at
2022-11-20 18:00
Duration
5 hour(s)
Host
Partic.
40