#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
const int N = 2e5 + 5;
// const int B = 400;
// const int M = 4e6 + 5;
// const int base = 15171;
// const int mod = 998244353;
// const i64 mod = (i64)1e18 + 7;
// const double pi = acos(-1);

int n, m, num[N];
i64 lst[N];
array<int, 2> a[N];
struct node
{
    int id;
    bool operator<(const node &tmp) const
    {
        if (num[id] == num[tmp.id])
            return id < tmp.id;
        return num[id] < num[tmp.id];
    }
};
void solve()
{
    cin >> n >> m;
    set<i64> times;
    map<i64, vector<int>> del;
    for (int i = 1; i <= n; i++)
        cin >> a[i][0] >> a[i][1], times.insert(a[i][0]);
    sort(a + 1, a + n + 1);
    set<node> st;
    for (int i = 1; i <= m; i++)
        st.insert({i});
    int p = 1;
    for (auto &t : times)
    {
        while (p <= n && a[p][0] == t)
        {
            auto [id] = *st.begin();
            st.erase({id});
            i64 cur = max((i64)a[p][0], lst[id]) + a[p][1];
            times.insert(cur);
            del[cur].push_back(id);
            num[id]++;
            lst[id] = cur;
            p++;
            st.insert({id});
        }
        if (del.count(t))
        {
            for (int i : del[t])
            {
                st.erase({i});
                num[i]--;
                st.insert({i});
            }
        }
    }
    cout << *max_element(lst + 1, lst + m + 1) << '\n';
    for (int i = 1; i <= m; i++)
        lst[i] = 0;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    // cout << fixed << setprecision(10);
    while (t--)
        solve();
}