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

using ll = long long;

void solve() {
	int n , m;
	cin >> n >> m;
	vector<array<int , 2> > a(n + 1);
	for(int i = 1 ; i <= n ; ++i) cin >> a[i][0] >> a[i][1];
	sort(a.begin() + 1 , a.end() , [](auto &x , auto &y) {
		return x[0] - x[1] < y[0] - y[1];
	});
	if(n == 1) {
		cout << a[1][1] << '\n';
		return;
	}
	ll ans = 0 , t = 0;
	int num = 0;
	vector<ll> pre(n + 1 , 0);
	for(int i = 1 ; i <= n ; ++i) {
		if(a[i][0] - a[i][1] >= 0 ) ++num;
		t += a[i][1];
		pre[i] = pre[i - 1] + a[i][0];
	}
	if(n + n - 1 <= m) ans = t;
	if(num == 1 && n >= 2) {
		t = a[n - 1][0] + a[n][0];
		for(int i = n - 2 ; i >= 1 ; --i) {
			if(a[i][0] - a[i][1] >= 0 ) {
				t += a[i][0];
				continue;
			}
			if(2 * i + (n - i) <= m) {
				t += a[i][1];
			}
			else t += a[i][0];
		}
		ans = max(ans , t);
		cout << ans << '\n';
		return;
	}
	int ok = 0 , i = n;
	t = 0;
	for(i = n ; i >= 0 ; --i) {
		if(a[i][0] - a[i][1] >= 0 ) {
			t += a[i][0];
			continue;
		}
		if(2 * i + (n - i) <= m) {
			t += a[i][1];
		}
		else t += a[i][0];
	}
	ans = max(ans , t);
	cout << ans << '\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt;
	cin>>tt;
	while(tt--) solve();
	return 0;
}