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


void solve() {
    int n, m;cin >> n >> m;
    vector<int>a(n + 1), b(n + 1);
    priority_queue<int>q;
    int sum = 0;
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        cin >> a[i] >> b[i];
        sum += b[i];
        q.push(a[i] - b[i]);
    }


    int x = m - n;
    if (n == 1) {
        cout << b[1] << "\n";return;
    }
    if (n == 2 and x >= 1) {
        cout << max(a[1] + a[2], b[1] + b[2]) << "\n";return;
    }

    //x空位
    if (2 * n - 1 <= m)
        ans = max(ans, sum);
    // cout << ans << "ans\n";
    int cnt = 0;
    sum += q.top(); q.pop();
    while (q.size()) {
        int u = q.top();q.pop();
        cnt++;
        sum += u;
        // cout << sum << "\n";
        if (2 * n - 1 - cnt <= m) {
            // cout << cnt << "\n";
            // cout << "ok\n";
            ans = max(ans, sum);
        }
    }
    cout << ans << "\n";

}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
#endif
    cin >> T;
    while (T--)
        solve();
    return 0;
}