#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll mod = 1000000007;

#define X first
#define Y second

ll pew(ll a, ll b)
{
    ll res = 1;
    while (b>0)
    {
        if (b&1) res = res*a%mod;
        b >>= 1;
        a = a*a%mod;
    }
}


const int N = 2048;

int dp[N][N];

void solve()
{
    for (int j=0;j<N;j++)
    {
        for (int i=0;i<N;i++) dp[j][i] = mod;
    }
    dp[0][1] = 0;
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i=0;i<n;i++) cin >> a[i];
    int A = mod;
    for (int i=0,i2=0;i<=n;i++,i2=(i2+1)%N)
    {
        for (int d=1;d<k;d++)
        {
            dp[i2][d+1] = min(dp[i2][d+1],dp[i2][d]);
            if ((i+k-d)>n) continue;
            dp[(i2+k-d)%N][k-d] = min(dp[(i2+k-d)%N][k-d],dp[i2][d]+a[i+k-d-1]);
        }
        if (i+k-1>=n) A = min(A,dp[i2][k-(n-i)-1]);
        for (int d=1;d<k;d++) dp[i2][d] = mod;
    }
    cout << A << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//#ifdef DEBUG
//    freopen("input.txt", "r", stdin);
//#endif
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}