#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define fi first
#define se second
#define all(_a) _a.begin(), _a.end()

void solve(){
    int n,m;
    cin>>n>>m;
    int sum=0;
    priority_queue<int>q;
    for(int i=1;i<=n;i++){
        m--;
        int x,y;
        cin>>x>>y;
        sum+=x;
        q.push(y-x);
    }
    int res=-INF;
    res=max(res,sum);
    if(n==1){
        cout<<res<<endl;
        return ;
    }
    if(n==2){
        if(m){
            sum+=q.top();
            q.pop();
            sum+=q.top();
            q.pop();
            res=max(res,sum);
        }
        cout<<res<<endl;
        return ;

    }
    while(q.size()&&m){
        
        if((q.size()==n)||(q.size()==n-1)){
            if(m==0)break;
            sum+=q.top();
            q.pop();
            res=max(res,sum);
            m--;
            continue;
        }
        if(m>=2){
            sum+=q.top();
            q.pop();
            res=max(res,sum);
            m-=2;
            continue;
        }else break;
    }
    cout<<res<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << setiosflags(ios::fixed) << setprecision(15);
    int T;
    T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}