选择恐惧症

英文题名：B. Decidophobia
来源：Codeforces 2239B
比赛：Codeforces Round 1105 (Div. 1)
时间限制：2 seconds
空间限制：256 megabytes

题目描述

有 $n$ 个人围成一圈。第 $i$ 个人权值为 $a_i$ ，视野为顺逆时针各 $d$ 人。收到礼物的人因视野内未收到礼物者获得快乐，未收到礼物的人因视野内收到礼物者产生负贡献。求总快乐值最大值。

第一行输入 $t$ 。每组输入 $n,d$ 和数组 $a$ 。

每组输出最大总快乐值。

5
3 1
1 2 3
5 1
1 4 5 2 6
6 2
1 1 4 5 1 4
10 2
230 24 3 42 432 234 934 2389 333 444
3 1
100000000 100000000 100000000