#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;
}