solution

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
bool c(pair<int, int> &a, pair <int ,int> &b) {
    return a.second - a.first>=b.second-b.first;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector <pair <int, int>> hachi(n), vip, us;
        for (int i = 0; i < n; i++) {
            cin >> hachi[i].first >> hachi[i].second;
            if (hachi[i].second>hachi[i].first) vip.emplace_back(hachi[i].first, hachi[i].second);
            else us.emplace_back(hachi[i].first, hachi[i].second);
        }
        sort(vip.begin(), vip.end(), c);
        ll k = us.size();
        ll ans = 0;
        if (k==1) {
            if (!vip.empty()) {
                if (m - vip.size()<2) {
                    for (int i = 0; i<n; i++) {
                        ans+=hachi[i].first;
                    }
                     cout << ans << '\n';
                    continue;
                } else {
                    vector <pair <int, int>> cur_vip = vip;
                    int left = cur_vip.size() - 1;
                    ll cur_ans = us[0].first + cur_vip[left].first;
                    cur_vip.erase(cur_vip.begin()+left);
                    ll cnt = 2 * cur_vip.size() - m + 2;
                    if (!cur_vip.empty() && cur_vip.size()-cnt>0) {
                        for (int i = 0; i<cur_vip.size() - cnt; i++) {
                            cur_ans+=cur_vip[i].second;
                        } for (int i = cur_vip.size() - cnt; i<cur_vip.size(); i++) {
                            cur_ans+=cur_vip[i].first;
                        }
                    }
                    if (vip.size() * 2 + 1<=m) {
                        for (int i = 0; i<vip.size(); i++) {
                            ans+=vip[i].second;
                        }cout << max(ans+us[0].second, cur_ans)<< '\n';
                        continue;
                    } else {
                        vip.push_back(us[0]);
                        sort(vip.begin(), vip.end(), c);
                        k = 2 * n - m;
                        if (n-k>0) {
                            for (int i = 0; i<n-k; i++) {
                                ans+=vip[i].second;
                            } for (int i = n - k; i<n; i++) {
                                ans+=vip[i].first;
                            }
                        }
                        cout << max(ans, cur_ans) << '\n';
                        continue;
                    }
                }
            } else {
                cout << us[0].second << '\n';
                continue;
            }
        } else if (k!=0){
            ll cnt = 2 * vip.size() + us.size() - m;
            for (int i = 0; i<us.size(); i++) {
                ans+=us[i].first;
            } if (!vip.empty() && vip.size() - cnt>0) {
                for (int i = 0; i<vip.size() - cnt; i++) {
                    ans+=vip[i].second;
                } for (int i = vip.size() - cnt; i<vip.size(); i++) {
                    ans+=vip[i].first;
                }
            } cout << ans << '\n';
        } else {
            if (n*2-1<=m) {
                for (int i = 0; i<vip.size(); i++) {
                    ans+=vip[i].second;
                } cout << ans << '\n';
            } else {
                ll k = 2 * n - m;
                if (k==1 && n==1) {
                    cout << hachi[0].second << '\n';
                    continue;
                } else if (k==1){
                    int ind, mn = 1000000000;

                    for (int i = 0; i<n; i++) {
                        if (vip[i].second - vip[i].first < mn) {
                            ind = i;
                            mn = vip[i].second - vip[i].first;
                        }
                    }for (int i = 0; i<n; i++) {
                        if (i == ind) {
                            ans+=vip[i].first;
                        } else {
                            ans+=vip[i].second;
                        }
                    } cout << ans << '\n';
                    continue;
                } else {
                    if (n-k>0) {
                        for (int i = 0; i<n-k; i++) {
                            ans+=vip[i].second;
                        } for (int i = n - k; i<n; i++) {
                            ans+=vip[i].first;
                        }
                    }
                     cout << ans << '\n';
                    continue;
                }
            }
        }
    }


    return 0;
}