1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 using namespace std; 5 #define max(a,b) (a>b?a:b) 6 int main() 7 { 8     double p,p1[105],dp[10005]; 9     int n,a[105],t,i,j;10     scanf("%d",&t);11     while(t--)12     {13         scanf("%lf%d",&p,&n);14         int sum=0;15         for(i=1;i<=n;i++)16         {17            scanf("%d%lf",&a[i],&p1[i]);18            p1[i]=1-p1[i];19            sum+=a[i];20         }21         memset(dp,0,sizeof(dp));22         dp[0]=1.0;23         for(i=1;i<=n;i++)24         {25             for(j=sum;j>=a[i];j--)26                dp[j]=max(dp[j],dp[j-a[i]]*p1[i]);27         }28         for(i=sum;i>=0;i--)29             if(1-dp[i]<p)30             {    31                 printf("%d\n",i);break;32             }33 34        35     }36   return 0;37 }