#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e6+10;
int t,n,m,ans;
struct node{
	int a,b;
}s[N];
bool cmp(node a,node b){
	return a.b-a.a>b.b-b.a;
}
signed main(){
	cin>>t;
	while(t--){
		cin>>n>>m;
		
		for(int i=1;i<=n;i++)
			cin>>s[i].a>>s[i].b;
		sort(s+1,s+1+n,cmp);
		
		int mid=1;
		while(mid<=n&&s[mid].b>s[mid].a)mid++;
		mid--;
		
		int tmp=m-mid*2ll-(n-mid);
		mid-=max(0ll,0-tmp);
		
		if(mid==n-1)
			if(s[n].a+s[n-1].a>s[n].b+s[n-1].b)
				mid--;
		
		while(mid>=2&&s[mid].a+s[mid-1].a>s[mid].a+s[mid-1].b)		
			mid--;
		
		ans=0;
		for(int i=1;i<=mid;i++)
			ans+=s[i].b;
		for(int i=mid+1;i<=n;i++)
			if(n>mid+1)
				ans+=s[i].a;
			else
				ans+=s[i].b;
		cout<<ans<<endl;
	}
	return 0;
}