//#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.a-a.b) < (b.a-b.b);
}
int main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&n,&m);
		zizizi=ans=tot1=tot2=0;
		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/2;
//		cout<<m<<" "<<awa<<" "<<ans<<" "<<zizizi<<" "<<tot1<<" "<<tot2<<endl;
		if(awa>=tot1) {
			printf("%lld\n",ans+zizizi);
			continue;
		}else{
			ll kkk=max(m-tot1,0ll);
			ll jian=0;
			for(int i=1;i<=tot1-kkk;i++)jian+=zi[i].a-zi[i].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