有$$$n$$$人参加圆桌聚会,按顺时针顺序编号为$$$1、2、3、\ldots、n$$$。你准备了一些礼物要分发给他们。
每个人 $$$i$$$ 都有一个体重 $$$a_i$$$ 和一个公共视野 $$$d$$$。 $$$i$$$ 人的视野由顺时针坐的 $$$d$$$ 人和逆时针坐的 $$$d$$$ 人组成(总共 $$$2d$$$ 人,不包括 $$$i$$$ 人)。
人$$$i$$$获得的幸福感由以下规则决定:
- 如果$$$i$$$收到礼物,并且在他们的视野内有$$$x$$$人没有收到礼物,他们会获得$$$x \cdot a_i$$$幸福。
- 如果$$$i$$$没有收到礼物,并且在他们的视野内有$$$x$$$人收到了礼物,他们会产生$$$-x \cdot a_i$$$幸福。
您希望最大化所有 $$$n$$$ 人的总幸福感。求这个最大值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le d \lt \frac{n}{2}$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^8$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个人的体重。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出一个表示最大总幸福感的整数。
示例
输入复制
53 11 2 35 11 4 5 2 66 21 1 4 5 1 410 2230 24 3 42 432 234 934 2389 333 4443 1100000000 100000000 100000000
输出复制
3152685900
注意
在第一个测试用例中,有 3 个人围坐一圈。对于每个人$$$i$$$,视野为$$$d=1$$$,其中包括顺时针坐的1个人和逆时针坐的1个人。如果人 2 收到礼物,他们会从 2 个没有收到礼物的邻居那里获得快乐,从而产生 $$$2 \cdot a_2 = 2 \cdot 2 = 4$$$。然而,人 1 和人 3 却遭受了损失,因为他们没有收到礼物,但有邻居收到了礼物。计算完所有可能性后,最大的总幸福感为3。
在第二个测试用例中,$$$n=5,d=1$$$。最好的方案是给2、3、5号人送礼物,这样可以达到最大的总幸福值15。