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.

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.

Decidophobia

Examples