//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
#define fr(a) freopen(a,"r",stdin)
#define fw(a) freopen(a,"w",stdout)
using namespace std;
typedef long long ll;
const int MAXN=5e5+10;
struct node{
	ll a,b;
}zi[MAXN],lin[MAXN];
ll T,n,m,x,y;
ll tot1,tot2,ans,zizizi;
bool cmp(node a,node b){
	return (a.b-a.a) > (b.b-b.a);
}
int main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&n,&m);
		zizizi=ans=tot1=tot2=0;
//		memset(zi,0,sizeof zi);
//		memset(lin,0,sizeof lin);
		for(int i=1;i<=n;i++){
			scanf("%lld%lld",&y,&x);
			//x独自 y邻居 
			if(x>y){ 
				zi[++tot1]=(node){x,y};
				zizizi+=x;
			}
			else {
				lin[++tot2]=(node){x,y};
				ans+=y;
			}
		}
		if(tot2==1){
			ans=lin[1].a;
		}
		m-=tot2;
		ll awa=(m+1)/2;
		sort(zi+1,zi+tot1+1,cmp);
//		cout<<m<<" "<<awa<<" "<<ans<<" "<<zizizi<<" "<<tot1<<" "<<tot2<<endl;
		if(awa>=tot1) {
			if(tot2==1 && lin[1].b+zi[1].b > lin[1].a +zi[1].a){
				printf("%lld\n",zizizi+lin[1].b-zi[1].a+zi[1].b);
			}
			else printf("%lld\n",ans+zizizi);
			continue;
		}else{
			ll kkk=m-tot1;
			ll jian=0;
//			cout<<"kkk:"<<kkk<<" tot1:"<<tot1<<endl;
			for(int i=1;i<=tot1-kkk;i++)jian+=zi[i].b-zi[i].a;
			if(tot2==1) ans=lin[1].b;
			printf("%lld\n",ans+zizizi+jian);
		}
	}
	return 0;
}
//3
//4 5
//1 100
//100 1
//100 1
//100 1
//2 2
//1 10
//1 10
//2 3
//100 50
//1 1000

//1
//4 6
//1 10000
//1 1000
//1 100
//2 3

//1
//3 5
//10000 1
//2 2000
//3 300

//1
//3 5
//100 1
//2 2000
//3 3000