#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
#define int long long
typedef pair<int, int> PII;
PII e[N];
#define x first
#define y second
bool cmp(PII a, PII b)
{
    if (a.y < b.y)
        return true;
    else if (a.y == b.y)
        return a.x > b.x;
}
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<int> s(n + 1, 0);
    for (int i = 1; i <= n; i++)
        cin >> e[i].x >> e[i].y;
    sort(e + 1, e + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + e[i].x;
    int ans = s[n];
    if (m == n)
    {
        cout << ans << '\n';
        return;
    }
    int vis = 0;
    for (int i = n, j = 1; i >= 1, j <= n; i--, j++)
    {
        vis += e[i].y;
        if (j == n - 1)
        {
            vis += e[1].y;
            if (j * 2 <= m + 1)
                ans = max(ans, vis);
            break;
        }
        if (i == 1 && j * 2 <= m + 1)
            ans = max(ans, s[i - 1] + vis);
        else if (i - 1 + j * 2 <= m)
            ans = max(ans, s[i - 1] + vis);
    }
    cout << ans << '\n';
}

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

    while (t--)
        solve();
    return 0;
}