#include<bits/stdc++.h>

#define ll long long
#define ull unsigned long long
#define db double
#define mkt make_tuple
#define mkp make_pair
#define pii pair<int, int>
#define vc vector
#define pb emplace_back

#define int long long

using namespace std;

const int N = 1e6 + 5, P = 1e9 + 7;
//const int inf = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
mt19937 gen(time(0));

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x;
}
inline void write(int x) {
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
inline void writec(int x) { write(x); putchar(32); }
inline void writee(int x) { write(x); putchar(10); }

inline void inc(int &x, int y) { x += y - P; x += (x >> 31) & P; }
inline void dec(int &x, int y) { x -= y; x += (x >> 31) & P; }
inline int pls(int x, int y) { x += y - P; x += (x >> 31) & P; return x; }
inline int power(int a, int b) { int res = 1; for(;b ; b >>= 1, a = 1ll * a * a % P) if(b & 1) res = 1ll * res * a % P; return res; }

int n, m, lmt, a[N], b[N], cnt[N], c[N], vis[N];

inline bool check(int v) {
	priority_queue<pii> Q; __int128 res = (__int128) v * m; int now;
	for(int i = 1; i <= n; i++) {
		c[i] = vis[i] = 0;
		Q.push(mkp(b[i], i));
		if(cnt[i] < v && a[i] % b[i]) Q.push(mkp(1, i));
	}
	while(!Q.empty() && res) {
		int x = Q.top().second, s;
		Q.pop();
		s = vis[x] ? 1 : min(v, cnt[x]); ++vis[x];
		s = min((__int128)s, res); c[x] += s; res -= s;
	}
	res = 0;
	for(int i = 1; i <= n; i++) {
		now = max(0ll, a[i] - b[i] * c[i]);
		//cerr << a[i] << " " << b[i] << " " << c[i] << " " << now << endl;
		if(now) res += 1 + max(0ll, now - b[i]);	
	}
	return res <= m;
}
 
inline void solve() {
	n = read(); m = read(); lmt = 1e9 * n;
	for(int i = 1; i <= n; i++) a[i] = read(), b[i] = read(), cnt[i] = a[i] / b[i];
	int l = 0, r = lmt, mid;
	while(l <= r) 
		if(check(mid = l + r >> 1)) r = mid - 1;
		else l = mid + 1;
	writee(l);
}

signed main() {
	int t = read(); while(t--) solve();
	return 0;
}