#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int mod = 1e9 + 7;
struct node
{
    int a;
    int b;
    int c;
} s[1000005];
bool cmp(node A, node B)
{
    return A.c < B.c;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        int k;
        if (((m + 1) / 2) >= n)
            k = n;
        else
            k = m - n;
        for (int i = 1; i <= n; i++)
        {
            cin >> s[i].a >> s[i].b;
            s[i].c = s[i].a - s[i].b;
        }
        sort(s + 1, s + n + 1, cmp);
        if (n == 1)
        {
            cout << s[1].b << endl;
        }
        else if (n - k <= 1)
        {
            int temp1 = s[n].a + s[n - 1].a;
            int temp2 = 0;
            for (int i = 1; i <= n - 2; i++)
            {
                if (s[i].c < 0)
                {
                    temp1 += s[i].b;
                }
                else
                {
                    temp1 += s[i].a;
                }
            }
            for (int i = 1; i <= n; i++)
            {
                temp2 += s[i].b;
            }
            cout << max(temp1, temp2) << endl;
        }
        else
        {
            int sum = 0;
            for (int i = 1; i <= n; i++)
            {
                if (s[i].c < 0 && k > 0)
                {
                    sum += s[i].b;
                    k--;
                }
                else
                {
                    sum += s[i].a;
                }
            }
            cout << sum << endl;
        }
    }

    return 0;

} /*Orz Orz Orz ACACAC*/