#include <bits/stdc++.h>

using namespace std;

const int MX = 100000;

int a[MX], dp[23][MX], f[23][MX];

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, m;
		scanf("%d %d", &n, &m);
		for (int i = 0; i < n; i++) scanf("%d", a + i);
		
		sort(a, a + n);
	
		vector<int> x = {-1};
		vector<int> sum = {0};
		for (int i = 0, s = 0; i < n; i++) {
			s += a[i];
			if (i < 11 || n - i - 1 < 11) {
				x.push_back(i);
				sum.push_back(s);
			}
		}
		
		for (int s = 0; s <= m; s++) f[0][s] = 1e9;
		for (int s = 0; s <= m; s += n) f[0][s] = 0;
		
		for (int i = 1; i < x.size(); i++) {
			int R = x[i];
			for (int s = 0; s <= m; s++) {
				dp[i][s] = 1e9;
				for (int j = 0; j < i; j++) {
					int L = x[j];
					
					dp[i][s] = min(dp[i][s], f[j][s] + sum[j] * (R - L));
				}
				
				f[i][s] = dp[i][s];
				if (s >= n - R - 1) f[i][s] = min(f[i][s], f[i][s - (n - R - 1)]);
			}
		}
		
		printf("%d\n", dp[x.size() - 1][m]);
	}
	
	return 0;
}