#include "bits/stdc++.h"
#define int long long
using namespace std;
int n, m;

void solve()
{
    cin >> n >> m;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin() + 1, a.end(), [&](pair<int, int> i, pair<int, int> j)
         { return i.second - i.first > j.second - j.first; });
    vector<vector<int>> pre(2, vector<int>(n + 1));
    for (int i = 1; i <= n; i++)
    {
        // cout << a[i].first << " " << a[i].second << endl;
        pre[0][i] = pre[0][i - 1] + a[i].second;
        pre[1][i] = pre[1][i - 1] + a[i].first;
    }
    // cout << "----------------------\n";
    int ans = 0;
    for (int i = 0; i <= n; i++)
    {
        int R = n - i;
        // cout << pre[0][i] << " " << pre[1][n] - pre[1][i] << endl;
        if (R == 1)
            continue;
        if (!R && 2 * i - 1 > m)
            break;
        if (R && 2 * i + R > m)
            break;
        ans = max(ans, pre[0][i] + pre[1][n] - pre[1][i]);
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}