#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int c[10005],v[10005];
int n,k;

bool check(int x){
    vector<int> a(n);
    for (int i=0;i<n;i++){
        a[i]=v[i]-x*c[i];
    }
    sort(a.begin(),a.end(),greater<int>());
    ll sum=0;
    for (int i=0;i<k;i++){
        sum+=a[i];
    }
    if (sum>=0) return 1;
    return 0;
}

void solve(){
    cin>>n>>k;

    for (int i=0;i<n;i++){
        cin>>c[i]>>v[i];
    }
    int l=0,r=10004;
    while (l<r){
        int mid= l+(r-l)/2;
        if (check(mid)){
            l=mid+1;
            
        }
        else
        r=mid;
    }
    cout<<l-1<<'\n';
    
}

int main(){
    int t;
    cin>>t;
    while (t--) solve();
    return 0;
}