#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;

int main(){
	int T;
	cin >> T;
	while(T--){
		int n,m;
		cin>>n;//人数 
		cin>>m;//房间数 
		unsigned long long ans = 0;
		vector<pair<int,int>> val(n);
		int a;
		int b;
		//a是有邻居，假设一开始所有人都有邻居 
		for(int i = 0; i < n; i++){
			cin >> a >> b;
			val[i] = make_pair(b-a, a);
		}
		sort(val.begin(),val.end());
		for(auto it:val)
		{
			//cout<<it.first<<" "<<it.second<<endl;
			ans+=it.second;
		 } 
		// cout<<"all adj"<<ans<<endl; 
		int right=n-1;
		int interval=0;
		if(m-n>=n-1)interval=n;
		else interval=min(m-n,n);
		//cout<<"interval="<<interval<<endl;
		int num_of_adj=n;
		if(n==1)
		{
			ans=val[0].first+val[0].second;
		}
		else
		{
		    while(val[right].first>0&&interval>0&&right>0)
			{
				if(num_of_adj>2)
				{
					ans+=val[right].first;
					right--;
					num_of_adj--;
					interval--;
				}
				//两个，看分开两个和是否大于0 
				else
				{
					int plus=val[right].first+val[right-1].first; 
					if(plus>0)
					{
						ans+=plus;
					}
					break;
				}
			}
		}
		cout<<ans<<endl;
		//cout<<"-------------------"<<endl;
	
	}
	return 0;
}