#include <bits/stdc++.h>
using namespace std;
using LL = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }

    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](const int &x, const int &y) {
        return a[x] - b[x] > a[y] - b[y];
    });

    LL ans = 0;

    if (m >= 2 * n - 1) {
        LL res = 0;
        for (int i = 0; i < n; ++i) {
            res += b[i];
        }
        ans = max(ans, res);
    }

    vector<LL> suma(n + 1), sumb(n + 2);
    for (int i = 0; i < n; ++i) {
        suma[i + 1] = suma[i] + a[id[i]];
    }
    for (int i = 0; i < n; ++i) {
        sumb[i + 1] = sumb[i] + b[id[n - i - 1]];
    }

    for (int i = n; i >= 2; --i) {
        LL t = (n - i) * 2;

        if (i + t > m) {
            break;
        }

        ans = max(ans, suma[i] + sumb[n - i]);
    }

    cout << ans << '\n';

}

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