#include<bits/stdc++.h>
#define int long long

using namespace std;

bool cmp(pair<int, int> &A, pair<int, int> &B) {
    return (A.second - A.first) > (B.second - B.first);
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    int t;

    cin >> t;

    while (t--) {
        int n, m;

        cin >> n >> m;

        int k = m - n;

        int s = 0, s2 = 0;

        vector<pair<int, int>> a(n);

        for (auto &[u, v]: a) {
            cin >> u >> v;
            s += u;
            s2 += v;
        }

        sort(a.begin(), a.end(), cmp);

        int res = s;

        int ss = s;

        for (int i = 0 ; i < n ; i++) {
            if(i*2 + (n-i) > m) continue;
            s += a[i].second - a[i].first;
            if (i < n-2) {
                res = max(res, s);
            }
        }

        if(n*2-1 <=m) {
            res = max(res, s2);
        }

        cout << res << "\n";
    }
    return 0;
}