#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define rep(i, l, r) for (int i = l; i < r; ++i)
#define per(i, r, l) for (int i = r-1; i >= l; --i)
typedef long long ll;
typedef pair<int, int> PI;
template<typename T> bool setmax(T &a, T b) { return (a < b ? a = b, 1 : 0); }
template<typename T> bool setmin(T &a, T b) { return (a > b ? a = b, 1 : 0); }


void solve() {
    int n,m;
    cin>>n>>m;
    vector<int> a(n),b(n),nh,h;
    ll ans=0;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        if(a[i]>=b[i]){ans+=a[i];m--;h.push_back(i);}
        else nh.push_back(i);
    }

    if(h.size()==0&&nh.size()*2-1<=m){
        for(int i=0;i<nh.size();i++){
            ans+=b[nh[i]];
        }
        cout<<ans<<'\n';
        return;
    }
    vector<pair<int,int>> c(nh.size());
    for(int i=0;i<nh.size();i++){
        c[i]={b[i]-a[i],nh[i]};
    }
    sort(c.begin(),c.end());

    if(h.size()==1&&nh.size()*2<=m){
        ans=0;
        if(nh.size()==0){
            ans=b[h[0]];
            cout<<ans<<'\n';
            return ;
        }
        for(int i=1;i<c.size();i++){
            ans+=b[c[i].second];
        }
        ans+=max(a[h[0]]+a[c[0].second],b[h[0]]+b[c[0].second]);
        cout<<ans<<'\n';
        return;
    }
    int i=0;
    int d=c.size();
    while(i<c.size()&&d*2>m){
        ans+=a[c[i].second];
        i++;
        d--;
        m--;
    }
    for(;i<c.size();i++){
        ans+=b[c[i].second];
    }
    cout<<ans<<'\n';

}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int tt; cin >> tt;
    while (tt--) solve();

    return 0;
}