#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n, d;
    cin >> n >> d;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<long long> a_new(3 * n);
    for (int i = 0; i < 3 * n; i++) {
        a_new[i] = a[i % n];
    }
    vector<long long> P(3 * n + 1, 0);
    for (int i = 0; i < 3 * n; i++) {
        P[i + 1] = P[i] + a_new[i];
    }
    long long max_total_happiness = 0;
    for (int i = 0; i < n; i++) {
        int center = n + i;
        long long window_sum = P[center + d + 1] - P[center - d];
        long long C_i = (2LL * d + 1) * a[i] - window_sum;
        if (C_i > 0) {
            max_total_happiness += C_i;
        }
    }
    cout << max_total_happiness << "\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}