#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
			.time_since_epoch().count());
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

using ll = long long;
using ld = double;

const int maxn = 1e5 + 100, inf = 1e9 + 100;

void solve() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> vec;
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        vec.emplace_back(a, b);
    }
    if (N == 1) {
        cout << vec[0].second << "\n";
        return;
    }
    sort(vec.begin(), vec.end(), [](pair<int, int> a, pair<int, int> b){
        return a.second - a.first > b.second - b.first;
    });
    long long sum = 0;
    for (auto p : vec) {
        sum += p.first;
    }
    long long ans = sum;
    for (int i = 1; i <= N - 2; i++) {
        if (2 * i + (N - i) <= M) {
            sum += vec[i - 1].second - vec[i - 1].first;
            ans = max(ans, sum);
        }
        else {
            break;
        }
    }
    if (M >= 2 * (N - 1) + 1) {
        sum += vec[N - 1].second - vec[N - 1].first;
        sum += vec[N - 2].second - vec[N - 2].first;
        ans = max(ans, sum);
    }
    cout << ans << "\n";
}

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
//    freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(20);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    cerr << "\n\nConsumed " << TIME << endl;
}