// Problem: D. New Houses
// Contest: Codeforces - The 2023 Guangdong Provincial Collegiate Programming Contest
// URL: https://codeforces.com/gym/104369/problem/D
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

/*
   /\__/\
  (o    o)
  /      \
 // ^  ^ \\
///      \\\
  \      /
   \____/
  /\_  _/\
 */
#include<bits/stdc++.h>

#define fir first
#define sec second
#define pb push_back
#define lowbit(X) X&(-X)
#define sz(X) (int)(X).size()
#define all(X) (X).begin(),(X).end()

#define YES cout<<"YES"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define NO cout<<"NO"<<'\n'
#define No cout<<"No"<<'\n'
#define error cout<<"-1"<<'\n'

using namespace std;
typedef long long unt;
typedef long double ld;
typedef vector<int> vt_int;
typedef vector<char> vt_char;
typedef vector<bool> vt_bool;
typedef vector<long long> vt_unt;
typedef vector<long double> vt_ld;
typedef vector<vector<int> > vvt_int;
typedef vector<vector<char> > vvt_char;
typedef vector<vector<bool> > vvt_bool;
typedef vector<vector<long long> > vvt_unt;
typedef vector<vector<long double> > vvt_ld;

const long long mod=1e9+7;
const long long INF=1152921504606846976;//(2^60)
const long long N=110000;

int solve(){
    unt n,m;
    cin>>n>>m;
    vt_unt d(n);
    vt_unt a(n),b(n);
    unt ans=0;
	for(int i=0;i<n;i++){
		cin>>a[i]>>b[i];
		d[i]=b[i]-a[i];
		ans+=a[i];
	}
	
	if(n==1){
		cout<<b[0]<<endl;
		return 0;
	}
	
	
	sort(all(d));
	reverse(all(d));
	
	if(m==3){
		if(n==2){
			ans=max(ans,b[0]+b[1]);
			cout<<ans<<endl;
			return 0;
		}
		if(n==3){
			cout<<ans<<endl;
			return 0;
		}
		if(n==1){
			cout<<b[0]<<endl;
			return 0;
		}
	}
	
	if(2*n-1<=m){
		unt res=0;
		for(int i=0;i<n;i++){
			res+=b[i];
		}
		ans=max(ans,res);
	}


	unt cnt=0;
	for(auto e:d){
		if(e<=0)break;
		cnt++;
		if(cnt==n-2)break;
		unt need=2*cnt+(n-cnt);
		if(need<=m){
			ans+=e;
		}
		else{
			break;
		}
	}
	cout<<ans<<endl;
    return 0;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int testcase;
    testcase=1;
    cin>>testcase;
    while(testcase--){
        int flag=solve();
        
        if(flag==1) YES;
        if(flag==-1) NO;
    }
    return 0;
}