#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e5+5;
vector<pair<int,int>> neibor,noneibor;

bool cmp(pair<int,int> aa,pair<int,int> bb){return aa.second > bb.second;}

void solve()
{
    neibor.clear();noneibor.clear();
    int n,m;cin>>n>>m;
    for(int i = 1;i<=n;i++)
    {
        int a,b;cin>>a>>b;
        if(a >= b) neibor.push_back({a,b});
        else noneibor.push_back({a,b});
    }
    //cout<<neibor.size()<<" "<<noneibor.size()<<endl;
    if(n == 1)
    {
        if(!neibor.empty()){cout<<neibor[0].second;}
        else cout<<noneibor[0].second;
        return;
    }
    sort(noneibor.begin(),noneibor.end(),cmp);
    int ans = 0;
    int size = neibor.size();
    int end = m - size;
    int cnt = end - noneibor.size();

    if(cnt >= noneibor.size())
    {
        if(neibor.size() == 1)
        {
            int tmp = neibor[0].first + noneibor[0].first;
            ans = max(tmp,neibor[0].second + noneibor[0].second);
            for(int i = 1;i<noneibor.size();i++)
            {
                ans += noneibor[i].second;
            }
        }
        else
        {
            for(int i = 0;i<neibor.size();i++)
            {
                ans += neibor[i].first;
            }
            for(int i = 0;i<noneibor.size();i++)
            {
                ans += noneibor[i].second;
            }
        }
    }
    else
    {
        for(int i = cnt;i<noneibor.size();i++)
        {
            neibor.push_back(noneibor[i]);
        }
        if(neibor.size() == 1)
        {
            int tmp = neibor[0].first + noneibor[0].first;
            ans = max(tmp,neibor[0].second + noneibor[0].second);
            for(int i = 1;i<cnt;i++)
            {
                ans += noneibor[i].second;
            }
        }
        else
        {
            for(int i = 0;i<neibor.size();i++)
            {
                ans += neibor[i].first;
            }
            for(int i = 0;i<cnt;i++)
            {
                ans += noneibor[i].second;
            }
        }
    }
    cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}