1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #define ll long long 7  8 using namespace std; 9 const int N = 1e4+1000;10 11 double dp[N];12 13 void solve()14 {15     int n;16     double p;17     int v[120],sum = 0;18     double w[120];19     scanf("%lf %d",&p,&n);20     p = 1.0 - p;21     for(int i = 0; i < n; i++)22     {23         scanf("%d %lf",&v[i],&w[i]);24         w[i] = 1.0 - w[i];25         sum += v[i];26     }27 28     memset(dp,0,sizeof(dp));29     dp[0] = 1.0;30     int ans = 0;31     for(int i = 0; i < n; i++)32     {33         for(int j = sum; j >= v[i]; j--)34             dp[j] = max(dp[j],dp[j-v[i]]*w[i]);35     }36 37     for(int i = 0; i <= sum; i++)38         if(dp[i] - p >= 1e-8)39             ans = max(ans,i);40     printf("%d\n",ans);41 }42 43 int main(void)44 {45     int t,cnt = 0;46     scanf("%d",&t);47 48     while(t--)49     {50         printf("Case %d: ",++cnt);51         solve();52     }53     return 0;54 }