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

using i64 = long long;

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

	for (int i = 0; i < n; ++i) {
		a[i] -= b[i];
	}
	sort(a.rbegin(), a.rend());

	vector<i64> sum(n + 1);

	for (int i = 1; i <= n; ++i) {
		sum[i] += sum[i - 1] + a[i - 1];
	}

	i64 ans = accumulate(b.begin(), b.end(), 0ll);
	i64 maxx = 0;
	if (2 * n - 1 <= m) {
		maxx = ans;
	}
	for (int i = 2; i <= n; ++i) {
		int j = n - i;
		if (2 * j + i <= m) {
			maxx = max(maxx, ans + sum[i]);
		}
	}
	cout << maxx << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}