#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 2e5+7,mod=1e9+7,INF=1e18;

void solve(){
	int n, m;
	cin >> n >> m;
	vector<pair<int,int>>a;
	ll ans = 0, last = m, du = 0, dv = 0;
	for(int i = 1; i <= n; i++) {
		int u, v; cin >> u >> v;
		if(u >= v) {
			du = u, dv = v; 
			ans += u;
			last--;
		} else {
			a.emplace_back(u, v);
		}
	}
	if(a.empty()) {
		cout << ans << "\n";
		return;
	}
	sort(a.begin(), a.end(), [&](auto o1, auto o2) {
		return o1.second - o1.first < o2.second - o2.first;	
	});
	if(ans == 0) {
		if((m + 1) / 2 >= n) {
			for(auto [u, v]:a) ans += v;
			cout << ans << "\n";
			return;
		} else {
			ans += a[0].first + a[1].first;
			last -= 2;
			a.erase(a.begin());
			a.erase(a.begin());
		}
	} else if(a.size() + 1 == n) {
		ll ans1 = 0, ans2 = 0;
		if(last / 2 >= a.size()) {
			for(auto [u, v]: a) ans1 += v;
			ans1 += dv;
			ans2 = ans1 - dv + du - a[0].second + a[0].first; 
			cout << max(ans1, ans2) << "\n";
			return;
		}
	}
	
	for(int i = 0; i < a.size(); i++) {
		auto [u, v] = a[i];
		if(last / 2 >= a.size() - i) {
			for(int j = i; j < a.size(); j++) ans += a[j].second;
			break;
		}
		
		last--;
		ans += a[i].first;
	}
	cout << ans << "\n";
	
}
int main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	ll T=1;
	
	cin>>T;
	
	while(T--){
		solve();
	}
	return 0;
}