1 #include<stdio.h>
 2 #include<string.h>
 3 int main()
 4 {
 5     int v[10001];
 6     double f[10001],w[10001];
 7     int i,j,n,m;
 8     int T;
 9     scanf("%d",&T);
10     while(T--)
11     {
12         double rate;
13         int sum=0;
14         scanf("%lf %d",&rate,&n);//rate被抓的概率，1-rate逃脱的概率 
15         for(i=0;i<n;i++)
16         {
17             scanf("%d %lf",&v[i],&w[i]);
18             sum+=v[i];
19         }
20         memset(f,0,sizeof(f));
21         f[0]=1;//没偷逃脱的概率为1 
22         for(i=0;i<n;i++)
23         {
24             for(j=sum;j>=v[i];j--)
25             {
26                 f[j]=f[j]>f[j-v[i]]*(1-w[i])?f[j]:f[j-v[i]]*(1-w[i]);//选择最大逃脱概率 
27             }
28         }
29         for(i=sum;i>=0;i--)
30         {
31             if(f[i]>=1-rate)
32             {
33             printf("%d\n",i);
34             break;
35            }
36         }
37     }
38     return 0;
39 }