Plan Holidays

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
#define int long long
struct nd {
    int mx[2][2];
    nd() {
        mx[0][0] = mx[0][1] = mx[1][0] = mx[1][1] = 0;
    }
    nd operator+(const nd& b) const {
        nd z;
        z.mx[0][0] = max({mx[0][0] + b.mx[0][0],mx[0][0] + b.mx[1][0],mx[0][1] + b.mx[0][0]});
        z.mx[0][1] = max({mx[0][0] + b.mx[0][1],mx[0][0] + b.mx[1][1],mx[0][1] + b.mx[0][1]});
        z.mx[1][0] = max({mx[1][0] + b.mx[0][0],mx[1][0] + b.mx[1][0],mx[1][1] + b.mx[0][0]});
        z.mx[1][1] = max({mx[1][0] + b.mx[0][1],mx[1][0] + b.mx[1][1],mx[1][1] + b.mx[0][1]});
        return z;
    }
};

// nd ept = nd();

struct seg {
    int n;
    vector<nd> tree;
    seg(int _n) : n(_n) {
        tree.assign(4*(n+1),nd());
    }
  
    void build(int l, int r, int p, vector<int>& a) {
        if (l == r) {
            tree[p].mx[1][1] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l,mid,p<<1,a);
        build(mid+1,r,p<<1|1,a);
        tree[p] = tree[p<<1] + tree[p<<1|1];
    }

    nd qr(int l, int r, int p, int x, int y) {
        // if (r < x || l > y) {
        //     return ept;
        // }
        if (l >= x && r <= y) {
            return tree[p];
        }
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return qr(l,mid,p<<1,x,y);
        } 
        if (x >= mid + 1) {
            return qr(mid+1,r,p<<1|1,x,y);
        }
        return qr(l,mid,p<<1,x,y) + qr(mid+1,r,p<<1|1,x,y);
    }
};


void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n+1);
    vector<int> pre(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i]; 
    }
    seg tree(n);
    tree.build(1,n,1,a);
    int ans = 1e18;
    // cout << tree.qr(1,1,n,1,5).mx[1][0] << endl;
    for (int i = 1; i + k - 1 <= n; i++) {
        ans = min(ans,pre[i+k-1] - pre[i-1] - tree.qr(1,n,1,i,i+k-1).mx[0][0]);
        if (i + k <= n) {
            ans = min(ans, pre[i + k] - pre[i - 1] -tree.qr(1, n, 1, i, i + k).mx[0][0]);
        }
    }
    cout << ans << '\n';
}   

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

        // if (r < x || l > y) {
        //     return ept;
        // }

        if (l >= x && r <= y) {
            return tree[p];
        }
        int mid = (l + r) >> 1;
        if (y <= mid) {
            return qr(l,mid,p<<1,x,y);
        } 
        if (x >= mid + 1) {
            return qr(mid+1,r,p<<1|1,x,y);
        }
        return qr(l,mid,p<<1,x,y) + qr(mid+1,r,p<<1|1,x,y);