#include<iostream>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 using namespace std;

 typedef long long ll;

 const int maxn=1e2+;

 double P;

 int n;

 int w[maxn];

 double p[maxn];

 double dp[];

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%lf%d",&P,&n);

         int sum=;

         for(int i=;i<=n;i++)

         {

             scanf("%d%lf",&w[i],&p[i]);

             sum+=w[i];

         }

         P=-P;

         for(int i=;i<=sum;i++) dp[i]=;

         dp[]=;

         for(int i=;i<=n;i++)

         {

             for(int j=sum;j>=w[i];j--)

             {

                 dp[j]=max(dp[j],dp[j-w[i]]*(-p[i]));

             }

         }

         for(int i=sum;i>=;i--)

         {

             if(dp[i]>P)

             {

                 printf("%d\n",i);

                 break;

             }

         }

     }

     return ;

 }