#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 = 2e5+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; i++)
   {
    ans+=v[i].a;
   }
     ll i = 0;
   for (; i < cnt and v[i].u>0 and i < n-1; i++)
   {
    ans-=v[i].a;
    ans+=v[i].b;
   }
   if(i==n-1){
    if((v[n-1].a+v[n-2].a)>(v[n-1].b+v[n-2].b)){
        ans+=v[n-2].a;
        ans-=v[n-2].b;
    }else{
        ans-=v[n-1].a;
        ans+=v[n-1].b;
    }
   }
   cout<<ans<<"\n";
}
int main(){
    ios;ll _=1;cin>>_;
    while (_--)solve();
    return 0;
}