include

include

using namespace std;
int main(){
int T,c[10005],v[10005];
int p[10005];
cin>>T;
while(T--){
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>c[i]>>v[i];
}
int l=1,r=10000,t=0;
while(l<=r){
int mid=(l+r)/2;
long long sum=0;
for(int i=0;i<n;i++){
p[i]=v[i]-c[i]*mid;
}
sort(p,p+n,greater<int>());
for(int i=0;i<k;i++){
sum+=p[i];
}
if(sum>=0){
if(mid>t)
t=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<<t<<endl;
}
return 0;
}</int>