#include <bits/stdc++.h>
#define VI vector<int>
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)
#define PII pair<int, int>
using namespace std;
struct typ
{
    int u, v, del;
    friend bool operator<(typ a, typ b)
    {
        return a.del < b.del;
    }
};

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<typ> a, b;
    for (int i = 1; i <= n; i++)
    {
        int u, v;
        cin >> u >> v;
        if (u >= v)
            b.push_back({u, v, u - v});
        else
            a.push_back({u, v, v - u});
    }
    sort(a.begin(), a.end()), sort(b.begin(), b.end());
    long long ans = 0;
    int need = a.size() * 2 + b.size();
    if (b.size() == 0)
        need--;
    if (m >= need)
    {
        long long sum1 = 0, sum2 = 0;
        for (auto it : a)
            sum1 += it.v;
        for (auto it : b)
            sum2 += it.u;
        if (b.size() == 1)
        {
            ans = max(ans, sum1 + b[0].v);
            if (a.size())
            {
                long long sum = sum1 - a[0].v + a[0].u + sum2;
                ans = max(ans, sum);
            }
        }
        else
        {
            ans = max(ans, sum1 + sum2);
        }
        cout << ans << "\n";
        return;
    }
    // 位置不gou
    int del = need - m;
    for (auto it : b)
        ans += it.u;
    if (a.size() > del)
    {
        for (int i = 0; i < del; i++)
            ans += a[i].u;
        for (int i = del; i < a.size(); i++)
            ans += a[i].v;
    }
    else if (n > 1)
    {
        ans = 0;
        for (auto it : a)
            ans += it.u;
        for (auto it : b)
            ans += it.u;
    }
    else
    {
        ans = 0;
        for (auto it : a)
            ans += it.v;
        for (auto it : b)
            ans += it.v;
    }

    cout << ans << "\n";
}

signed main()
{
    IOS;
    int T;
    cin >> T;
    while (T--)
        solve();

    return 0;
}