#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int min(int a,int b){
  return a>b?b:a;
}
void swap(int i,int j,int *skill,int *blood){
    int x=skill[i];
    skill[i]=skill[j];
    skill[j]=x;
    x=blood[i];
    blood[i]=blood[j];
    blood[j]=x;
}
int dfs(int n,int i,int *skill,int *blood,int b){
    if(b<=0)
      return i;
    if(i==n)
      return 2147483647;
    int ans=2147483647;
    for(int j=i;j<n;j++){
        swap(i,j,skill,blood);
        ans=min(ans,dfs(n,i+1,skill,blood,b-(b>blood[i]?skill[i]:skill[i]*2)));
        swap(i,j,skill,blood);
    }
    return ans;  
}
int main() {
    int a, b,n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d",&a,&b);
        int *skill=malloc(sizeof(int)*a);
        int *blood=malloc(sizeof(int)*a);
        for(int j=0;j<a;j++){
            scanf("%d %d",&skill[j],&blood[j]);
        }
        int ans=dfs(a,0,skill,blood,b);
        ans=ans==2147483647?-1:ans;
        printf("%d\n",ans);
        free(skill);
        free(blood);
    }
    return 0;
}