1 /*
 2 Author:    Leo.W
 3 Descriptipn:    搶銀行。搶每個(gè)銀行被抓的幾率為caught[]，互為獨(dú)立事件，在容忍上限內(nèi)，搶最多的錢(qián)。    
 4 How to Do:    01背包，但需要改變一點(diǎn)。需要將能搶來(lái)的最多的錢(qián)最為背包容量。
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10 #define max(a,b) a>b?a:b
11 double caught[102],DP[10001];
12 int money[102];
13 int main(){
14     //freopen("in.txt","r",stdin);
15     int t;
16     scanf("%d",&t);
17     while (t--){
18         double limit;
19         int banks;
20         scanf("%lf%d",&limit,&banks);
21         int i,j,sum=0;
22         for(i=0;i<banks;i++)
23             scanf("%d%lf",&money[i],&caught[i]),sum+=money[i];
24         memset(DP,0,sizeof(DP));
25         DP[0]=1.0;
26         for(i=0;i<banks;i++){
27             for(j=sum;j>=money[i];j--){
28                 DP[j]=max(DP[j],DP[j-money[i]]*(1-caught[i]));
29             }
30         }
31         for(i=sum;i>=0;i--){
32             if(DP[i]>=1-limit){
33                 printf("%d\n",i);
34                 break;
35             }
36         }
37     }
38     return 0;
39 }
40