#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int T;
ll n,m;
struct Node{
	ll a,b;
	bool operator<(const Node&W)const{
		return b-a>W.b-W.a;
	}
}node[N];

void init()
{
	cin>>n>>m;
	

	
	
	ll res = 0;
	ll mmax;
	for(int i=1;i<=n;i++){
		cin>>node[i].a>>node[i].b;
		res+=node[i].a;
	}
	if(n==1){
		cout<<node[n].b<<'\n';
		return;
	}
	mmax = res;
	sort(node+1,node+1+n);
	
	
	
	ll len = m-n;
	for(int i=1;i<=n-1;i++){
		
		if(len<1)break;
		
		len+=1;
	    len -= 2;
	    res -= node[i].a;
	    res += node[i].b;
	    
	    if(i==n-1)
	    {
	    	res -= node[n].a;
	    	res += node[n].b;
	    }
		
		mmax = max(res,mmax);
		
	}
	
	
	

	cout<<mmax<<'\n';
	
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		init();
	}
	return 0;
}