#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
using namespace std;
int a[1000005],b[1000005],c[1000005];
void solve(){
    int n,m;
    scanf("%d%d",&n,&m);
    ll ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
        c[i]=b[i]-a[i];
        ans+=a[i];
    }
    sort(c+1,c+n+1);
    for(int i=n;i>2;i--){
        if(c[i]>0&&m>=n+n-i+1){
            ans+=c[i];
        }
    }
    if(m>=n*2-1){
        ll cnt=0;
        for(int i=1;i<=n;i++){
            cnt+=b[i];
        }
        ans=max(ans,cnt);
    }
    printf("%lld\n",ans);
}
int main(){
    int t=1;
    scanf("%d",&t);
    while(t--)solve();
    return 0;
}