//hdu2955 #include<iostream> #include<cstdio> #include<vector> #include<string> #include<queue> #include<cmath> #include<algorithm> #include<cstring> #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 100005 #define INF 0xfffffff #define mem(a,b) memset(a,b,sizeof(a)) #define FOR(i,s,t) for(int i=s;i<=t;i++) #define ull unsigned long long #define ll long long using namespace std; int v[maxn]; double dp[maxn],p[maxn]; //dp[i]表示抢i元最大的不被抓到的概率 void init(int sum) { for(int i=0;i<=sum;i++) { dp[i]=-1; } } int main() { int t,n; double P; scanf("%d",&t); while(t--) { double P; scanf("%lf%d",&P,&n); int sum=0; for(int i=1;i<=n;i++) { scanf("%d%lf",&v[i],&p[i]); sum+=v[i]; } init(sum); dp[0]=1.0; for(int i=1;i<=n;i++) { for(int j=sum;j>=v[i];j--) { dp[j]=max(dp[j],1.0*dp[j-v[i]]*(1.0-p[i])); } } int ans=0; for(int i=sum;i>=1;i--) { if(dp[i]>=(1.0-P)) { ans=i; break; } } printf("%d\n",ans); } return 0; }