/*
[templates]: 
duipai
spjdp
compre
addhis
floor_sum
treedfs
matrix
network_flow
polynomial
lca
bitset
valuesgt
fenwick
erbitree
*/
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx")
#include<bits/stdc++.h>
using namespace std;
#define int long long
//use ll instead of int.
#define f(i, a, b) for(int i = (a); i <= (b); i++)
#define cl(i, n) i.clear(),i.resize(n);
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e18;
//#define cerr if(false)cerr
//#define freopen if(false)freopen
mt19937 rng(time(0)); 
int rnd(int l, int r) {return rng() % (r-l+1) + l; }
#define watch(x) cerr  << (#x) << ' '<<'i'<<'s'<<' ' << x << endl
void pofe(int number, int bitnum) {
    string s; f(i, 0, bitnum) {s += char(number & 1) + '0'; number >>= 1; } 
    reverse(s.begin(), s.end()); cerr << s << endl; 
    return;
}
template <typename TYP> void cmax(TYP &x, TYP y) {if(x < y) x = y;}
template <typename TYP> void cmin(TYP &x, TYP y) {if(x > y) x = y;}
//调不出来给我对拍！
//use std::array.
int t[200020], d[200020]; int n, c; 
int cost(int ti, int ki, int di) {
    if(ti - ki * di <= 0) return 0; 
    else if(ti - ki * di <= di) return 1; 
    else return ti - ki * di - di + 1; 
}
namespace geq {
    bool ok(int day) {
        int tot = 0; 
        f(i, 1, n) {
            tot += cost(t[i], day, d[i]); 
        }
        return tot <= c; 
    }
    void work() {
        int lo = 0, hi = 1e9; 
        while(lo < hi) {
            int mid = (lo + hi) >> 1; //留意一下是否会爆 long long. 
            if(ok(mid)) hi = mid; 
            else lo = mid + 1; 
        }
        cout << lo << endl; 
        return; 
    }
}
namespace brute1 {
    int dp[200020], tmp[200020]; 
    int mnday(int ti, int di, int want) { //want <= c. 
        if(want == 0) {
            //ti - di ret <= 0
            //di ret >= ti
            //ret >= ti / di 
            return (ti + di - 1) / di; 
        }
        else if(want == 1) {
            //实际上如果 cost(ti, ret, di) < want 的话也是可以的.
            //ti - di ret <= di
            //ret >= (ti - di) / di
            return (ti - 1) / di; 
        }
        else {
            //ti - ret di - di + 1 = want.
            //ret di = ti - di + 1 - want
            //if ti - di + 1 - want % di != 0, 是不行的！
            //需要 上取整. 
            //变成 (ti - want) / di. 
            //但是实际上这个是没啥用的啊。
            //感觉样例挺强的？
            return (ti - want) / di; 
        }
    }
    bool ok(int day) {
        // cerr << "day = " << day << endl; 
        vector<pii> vec; 
        int tot1 = 0; 
        int tot = 0; int totb = 0; 
        f(i, 1, n) {
            int wei0 = mnday(t[i], d[i], 0); 
            int wei1 = mnday(t[i], d[i], 1);
            // cerr << "i = " << i << ", wei0 = " << wei0 << ", wei1 = " << wei1 << endl;  
            if(wei0 <= day) {
                tot += wei0;
                tot1 ++; 
                // cerr << "choose " << wei0 << ", " << 0 << endl; 
                vec.push_back({cost(t[i], wei1 - 1, d[i]) - 1, 1}); 
                vec.push_back({d[i], wei1 - 1}); 
            }
            else if(wei1 <= day) {
                tot += wei1; 
                totb += 1; 
                // cerr << "choose " << wei1 << ", " << 1 << endl; 
                vec.push_back({cost(t[i], wei1 - 1, d[i]) - 1, 1}); 
                vec.push_back({d[i], wei1 - 1}); 
            }
            else {
                //a: day
                //b: 1 + d[i] * (wei1 - day)
                tot += day; 
                totb += cost(t[i], day, d[i]); 
                // cerr << "choose " << day << ", " << cost(t[i], day, d[i]) << endl; 
                vec.push_back({d[i], day}); 
            }
        }
        vec.push_back({1, tot1}); 
        sort(vec.begin(), vec.end()); 
        // cerr << "tot = " << tot << ", totb = " << totb << endl; 
        // for(pii i : vec) {
            // cerr << i.first << " " << i.second << endl; 
        // }
        if(tot <= day * c) return totb <= c; 
        int q = tot - day * c; int sum = 0; 
        // cerr << "q = " << q << endl; 
        //前 q 个的和
        for(pii i : vec) {
            if(i.second >= q) {
                // cerr << "q = " << q << endl;
                // cerr << "sum = " << sum << endl; 
                sum += q * i.first; 
                break;
            }
            else {
                sum += i.second * i.first; 
                // cerr << "sum = " << sum << endl; 
                q -= i.second; 
            }
        }
        // cerr << "sum = " << sum << endl; 
        return totb + sum <= c; 
    }
    void work() {
        int lo = 0, hi = 2e14; 
        while(lo < hi) {
            int mid = (lo + hi) >> 1; 
            if(ok(mid)) hi = mid; 
            else lo = mid + 1; 
        }
        cout << lo << endl; 
        return; 
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen();
    //freopen();
    //time_t start = clock();
    //think twice,code once.
    //think once,debug forever.
    int T; cin >> T; //注意多测清空。 
    while(T--) {
        cin >> n >> c; 
        f(i, 1, n) cin >> t[i] >> d[i]; 
        if(c >= n) geq::work(); 
        else brute1::work();
    }
    //time_t finish = clock();
    //cout << "time used:" << (finish-start) * 1.0 / CLOCKS_PER_SEC <<"s"<< endl;
    return 0;
}