#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;using ll = long long;using PLL = pair<ll,ll>;
const ll MAX = 1e18;const ll MIN = -1e18;const ll INF=0x3f3f3f3f;
const ll Q = 5e5+9;const ll MOD = 1e9 + 7;
struct Edge
{
    ll a,b,u;
};
vector<Edge> v;
bool cmp(Edge l,Edge r){
    return l.u>r.u;
}
void solve(){
    v.clear();
   ll n,m;cin>>n>>m;
   for (ll i = 1; i <= n; i++)
   {
    ll o,p;cin>>o>>p;
    ll q=(p-o);
    v.push_back({o,p,q});
   }
   sort(v.begin(),v.end(),cmp);
   ll cnt=m-n;
   ll ans=0;
   for (ll i = 0; i < n-2; i++)
   {
    if(cnt>0 and v[i].u>0){
        ans+=v[i].b;cnt--;
    }else{
        ans+=v[i].a;
    }
   }
   if(cnt>0 and (v[n-1].a+v[n-2].a)<(v[n-1].b+v[n-2].b)){
    ans+=v[n-1].b;
    ans+=v[n-2].b;
   }else{
    ans+=v[n-1].a;
    ans+=v[n-2].a;
   }
   cout<<ans<<"\n";
}
int main(){
    ios;ll _=1;cin>>_;
    while (_--)solve();
    return 0;
}