#include <bits/stdc++.h>
using namespace std;
#define int long long
int t,n,m,r1,r2,res;
struct node{
	int a,b;
	friend bool operator<(node a,node b){
		return a.a-a.b>b.a-b.b;
	}
}p[500005];
int solve(){
	int l=0,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(mid+2*(n-mid)<=m)r=mid;
		else l=mid+1;
	}
	if(2*n-1<=m)return 0;
	return l;
}
signed main(){
	cin>>t;
	while(t--){
		cin>>n>>m;r1=r2=0;res=0;
		for(int i=1;i<=n;i++){
		    scanf("%lld%lld",&p[i].a,&p[i].b);	
		    if(p[i].a>p[i].b)r1++;
		    else r2++;
		}
		sort(p+1,p+n+1);
	    int k=solve();
	    if((r1==1&&k<=1)||k==1){
	    	for(int i=1;i<=n;i++)res+=p[i].b;
	    	printf("%lld\n",res);
	    	continue;
	    }
	    if(r1>=k){
	    	for(int i=1;i<=n;i++)res+=max(p[i].a,p[i].b);
	    	printf("%lld\n",res);
	    	continue;
	    }
	    for(int i=1;i<=k;i++)res+=p[i].a;
	    for(int i=k+1;i<=n;i++)res+=p[i].b;
	    printf("%lld\n",res);
	}
}