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