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. 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). For each test case, output a single integer representing the maximum total happiness. 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 d