#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=5e5+10;
int t,n,m,ans;
struct node{
	int a,b;
}s[N];
bool cmp(node a,node b){
	if(a.b>a.a&&b.b>b.a)
		return a.b-a.a>b.b-b.a;
	if(a.b>a.a&&b.b<=b.a)
		return 1;
	if(a.b<=a.a&&b.b>b.a)
		return 0;
	return a.a>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(s[mid].b>s[mid].a)mid++;
		mid--;
		int tmp=m-mid*2-(n-mid);
		mid-=max(0ll,0-tmp);
		ans=0;
		if(mid==n-1){
			if(s[n].a+s[n-1].a>s[n].b+s[n-1].b)
				mid--;
		}
		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;
}