#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define pii pair<ll, ll>

inline ll rd() {
    ll x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 200007

vector<pii> a;

queue<int> q[N];

set<pii> s, d;

inline bool nextp(int id) {
    s.erase(mp(q[id].size(), id)); q[id].pop();
    s.insert(mp(q[id].size(), id));
    return !q[id].empty();
}

inline void add(int id, int p) {
    //printf("%d %d\n", id, p);
    s.erase(mp(q[id].size(), id)); q[id].push(p);
    s.insert(mp(q[id].size(), id)); 
    if (q[id].size() == 1) d.insert(mp(a[p].fr + a[p].sc, id));
}

inline void work() {
    int n = rd(), m = rd(); a.clear();
    for (int i = 1; i <= n; ++i) {
        int ar = rd(), st = rd();
        a.push_back(mp(ar, st));
    }
    sort(a.begin(), a.end()); 
    s.clear();
    for (int i = 1; i <= m; ++i) s.insert(mp(0, i));
    for (int i = 0; i < n; ++i) {
        int nw = a[i].fr;
        while (!d.empty() && d.begin() -> fr <= nw) {
            ll tm = d.begin() -> fr;
            int id = d.begin() -> sc; 
            d.erase(d.begin());
            if (nextp(id)) d.insert(mp(tm + a[q[id].front()].sc, id));
        }
        auto id = s.begin() -> sc;
        add(id, i);
    }
    ll ans = 0;
    while (!d.empty()) {
        int id = d.begin() -> sc;
        ll tm = d.begin() -> fr;
        d.erase(d.begin());
        q[id].pop();
        while (!q[id].empty()) {
            tm += a[q[id].front()].sc; q[id].pop();
        }
        ans = max(ans, tm);
    }
    printf("%lld\n", ans);
} 

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}