#include <bits/stdc++.h>

#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
const int N = 5e5 + 10;

int n, m;
int a[N];

void solve() {
    LL ans = 0;
    cin >> n >> m;
    int pos = 0;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        a[i] = x - y;
        ans += y;
        if (a[i] >= 0) ++pos;
    }
    sort(a + 1, a + n + 1);
    m -= n;
    for (int i = 1; i <= n; ++i) {
        if (a[i] < 0 && m > 0) {
            --m;
            if (pos == 1 && a[i + 1] >= 0) {
                if (a[i + 1] > -a[i]) ans += a[i] + a[i] + 1;
                ++i;
            }
            continue;
        }
        ans += a[i];
    }
    cout << ans << '\n';
}

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