#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;
const int MX = 2002;
int a[MX*10], dp[MX][MX];

void solve() {
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for (int i = 0; i < m; i++) {
		dp[0][i] = 0;
	}
	
	int ans = INF;
	for (int i = 1; i <= n+1; i++) {
		for (int j = 1; j < m; j++) {
			dp[i % MX][j] = INF;
		}

		for (int j = 1; j < m; j++) {
			if (j > i) break;
			dp[i % MX][j] = min(dp[i % MX][j], dp[(i-j+MX) % MX][m-j] + a[i]);
		}

		for (int j = 2; j < m; j++) {
			dp[i % MX][j] = min(dp[i % MX][j], dp[i % MX][j-1]);
		}

		/*for (int j = 1; j < m; j++) {
			cout << dp[i][j] << ' ';
		}
		cout << '\n';*/

		if (i == n+1) {
			for (int j = 1; j < m; j++) {
				ans = min(ans, dp[i % MX][j]);
			}
		}
	}
	cout << ans << '\n';
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	
	int ts; cin >> ts;
	while (ts--) {
		solve();
	} 

	return 0;
}