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

#define int long long

typedef long long ll;

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

    int T;
    cin >> T;
    while(T -- ) {
        int n, m;
        cin >> n >> m;
        vector<array<int, 3>> arr(n);
        for(int i = 0; i < n; i ++ ) {
            cin >> arr[i][0] >> arr[i][1];
            arr[i][2] = arr[i][1] - arr[i][0];
        }
        sort(arr.begin(), arr.end(), [&](array<int, 3> x, array<int, 3> y) {
            return x[2] > y[2];
        });

        vector<ll> sufa(n + 1, 0);
        for(int i = n - 1; i >= 0; i -- ) sufa[i] = sufa[i + 1] + arr[i][0];

        ll ans = sufa[0], sumb = 0;
        for(int i = 0; i < n; i ++ ) {
            sumb += arr[i][1];
            if(arr[i][2] <= 0) break;
            if(2 * (i + 1) + n - i - 1 <= m && n - i - 1 >= 2) {
                ans = max(ans, sumb + sufa[i + 1]);
            }
        }
        if(n + n - 1 <= m) ans = max(ans, sumb);
        cout << ans << '\n';
    }
    return 0;
}