#include <bits/stdc++.h>

using namespace std;

const int N = 500010;

typedef long long ll;

struct node
{
    ll a,b;
    ll x;
    bool id;
}q[N];

int n,m;

bool fun(struct node x,struct node y)
{
    return x.x > y.x;
}

void solve()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        cin >> q[i].a >> q[i].b;
        if(q[i].a != q[i].b)
        {
            if(q[i].a > q[i].b)
            {
                q[i].id = 0;
            }
            else
            {
                q[i].id = 1;
            }
        }
        else
        {
            q[i].id = 0;
        }
        q[i].x = max(q[i].a,q[i].b);
    }
    
    sort(q + 1,q + 1 + n,fun);
    ll sum = 0;
    //for(int i = 1;i <= n;i++)cout << q[i].a <<' '<< q[i].b<<' '<<q[i].id<<endl;
    int l = 0;
    int r = m + 1;

    for(int i = 1;i <= n;i++)
    {
        if(q[i].id == 0)
        {
            if(i == n && r == m + 1)
            {
                sum += q[i].b;
                break;
            }
            sum += q[i].x;
            r--;
        }
        else
        {
            int seng = n - i;
            if(r - seng > l + 2)
            {
                sum += q[i].x;
                l += 2;
            }
            else
            {
                if(i == n && r == m + 1)
                {
                    sum += q[i].b;
                    break;
                }
                for(int j = i;j <= n;j++)sum += q[i].a;
                break;
            }
        }
        //cout <<'*'<<sum<<endl;
    }
    cout << sum<<'\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;

    while (t--)
        solve();
    return 0;
}