#include<bits//stdc++.h>
using namespace std;
#define RI register int
#define int __int128
inline int read() {
    RI x=0, w=0;register char ch=0;
    while(!isdigit(ch)) w|=ch=='-', ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    return w?-x:x;
}
const int MAXN=4e5+1;
int N, C, cnt, Need, a[MAXN], b[MAXN], used[MAXN];
pair<int,pair<int,bool> > c[MAXN];
inline bool judge(int x) {
	int tot=0, t=x*C;
	for(RI i=1;i<=cnt;i++) used[i]=0;
	for(RI i=1;i<=cnt;i++) {
		if(c[i].second.second) {
			int k=min({t,c[i].second.first,x});
			t-=k, tot+=k*c[i].first; used[i]=k;
		}
		else if(x>a[-c[i].second.first]/b[-c[i].second.first] && t) t--, used[i]=1, tot+=c[i].first;	
	} t=C;
	for(RI i=1;i<=cnt;i++) {
		if(c[i].second.second) {
			int k=min({t,c[i].second.first-used[i],(int)1});
			t-=k, tot+=k*c[i].first; 
		}
		else if(x>=a[-c[i].second.first]/b[-c[i].second.first] && t && !used[i]) t--, tot+=c[i].first;	
	} return tot+t>=Need;
}	
inline void solve() {
	N=read(), C=read(); cnt=Need=0;
	for(RI i=1;i<=N;i++) a[i]=read(), b[i]=read(), Need+=a[i]; 
	for(RI i=1;i<=N;i++) {
		c[++cnt]=make_pair(b[i],make_pair(a[i]/b[i],1));
		if(a[i]%b[i]!=0) c[++cnt]=make_pair(a[i]%b[i],make_pair(-i,0));
	} sort(c+1,c+cnt+1); reverse(c+1,c+cnt+1); 
	int l=0, r=2e14, mid; 
	while(l<=r) {
		mid=l+r>>1;
		if(judge(mid)) r=mid-1;
		else l=mid+1;	
	} printf("%lld\n",(long long)l);
}
signed main() {
//	freopen("a.in","r",stdin);
	int t=read(); while(t--) solve();
    return 0;
}// Kanbe_Kotori is kawaii qwq