B. Decidophobia
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ people attending a round-table party, numbered $$$1, 2, 3, \ldots, n$$$ in clockwise order. You have prepared some gifts to distribute among them.

Each person $$$i$$$ has a weight $$$a_i$$$ and a common field of view $$$d$$$. The field of view for person $$$i$$$ consists of the $$$d$$$ people sitting clockwise and the $$$d$$$ people sitting counter-clockwise from them (a total of $$$2d$$$ people excluding person $$$i$$$).

The happiness gained by person $$$i$$$ is determined by the following rules:

  • If person $$$i$$$ receives a gift, and there are $$$x$$$ people within their field of view who did not receive a gift, they gain $$$x \cdot a_i$$$ happiness.
  • If person $$$i$$$ does not receive a gift, and there are $$$x$$$ people within their field of view who received a gift, they incur $$$-x \cdot a_i$$$ happiness.

You want to maximize the total happiness of all $$$n$$$ people combined. Find this maximum value.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$d$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le d \lt \frac{n}{2}$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^8$$$), where $$$a_i$$$ is the weight of the $$$i$$$-th person.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer representing the maximum total happiness.

Example
Input
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
Output
3
15
26
8590
0
Note

In the first test case, there are 3 people sitting in a circle. For each person $$$i$$$, the field of view is $$$d=1$$$, which includes the 1 person sitting clockwise and the 1 person sitting counter-clockwise from them. If person 2 receives the gift, they gain happiness from 2 neighbors who did not receive it, resulting in $$$2 \cdot a_2 = 2 \cdot 2 = 4$$$. However, person 1 and person 3 incur loss because they did not receive a gift but have a neighbor who did. After calculating all possibilities, the maximum total happiness is 3.

In the second test case, $$$n=5, d=1$$$. The best solution is to give gifts to persons 2, 3, and 5, which can achieve the maximum total happiness value of 15.