CF2239B.Decidophobia

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.

有 $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$ 的幸福感（即损失 $x \cdot a_i$ 的幸福感）。

你希望最大化所有 $n$ 个人的总幸福感。求该最大值。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

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 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.

在第一个测试用例中，有 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。