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

using i64 = long long;

void solve() {
	int n, m;
	cin >> n >> m;
	vector<array<i64, 2>> a(n);
	vector<i64> x, y;
	for (int i = 0; i < n; ++i) {
		cin >> a[i][0] >> a[i][1];
		if (a[i][0] >= a[i][1]) {
			x.push_back(i);
		} else {
			y.push_back(i);
		}
	}
	if (x.size() == 1) {
		y.push_back(x.back());
		x.pop_back();
	}
	i64 ans = 0;
	for (int i = 0; i < x.size(); ++i) {
		ans += a[x[i]][0];
	}
	m -= x.size();
	sort(y.begin(), y.end(), [&] (auto &x, auto &y) {
		return a[x][1] >= a[y][1];
	});
	vector<i64> pre(y), pr(y);
	pre.insert(pre.begin(), 0);
	pr.insert(pr.begin(), 0);
	for (int i = 1; i < pre.size(); ++i) {
		pre[i] = pre[i - 1] + a[pre[i]][1];
		pr[i] = pr[i - 1] + a[pr[i]][0];
	}
	i64 maxx = ans;
	for (int i = 0; i <= y.size(); ++i) {
		int j = m - 2 * i;
		if (x.empty()) {
			if (j >= (int)y.size() - i) {
				if (j >= 2) {
					maxx = max(maxx, ans + pre[i] + pr.back() - pr[i]);
				} else {
					maxx = max(maxx, ans + pre[i + 1]);					
				}
			}
		} else if (j >= (int)y.size() - i) {
			maxx = max(maxx, ans + pre[i] + pr.back() - pr[i]);
		}
	}
	cout << maxx << '\n';
}

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

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