#include <iostream>

#include <string>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <stack>

using namespace std;

#define MEM(a,b) memset(a,b,sizeof(a))

#define pf printf

#define sf scanf

#define debug printf("!/m")

#define INF 8000

#define MAX(a,b) a>b?a:b

#define blank pf("\n")

#define LL long long

#define ep 1e-6

double dp[INF];

double ci[INF];//容量

int wi[INF];//价值

int n,V,i,j,v,t,sum;

double vi;

void zeroOnePack(int cost,double weight)

{

          for(v = sum;v>=cost;v--)

          {

                    dp[v] =MAX(dp[v],dp[v-cost]*weight);

          }

}

void completePack(int cost,int weight)

{

          for(v = cost;v<=V;v++)

          {

                    dp[v] =MAX(dp[v],dp[v-cost]+weight);

                    pf("tt%d %d %d\n",i,v,dp[v]);

          }

}

int main()

{

          sf("%d",&t);

          while(t--)

          {

                    sf("%lf%d",&vi,&n);

                    MEM(dp,);

                    dp[] = 1.0;

                    MEM(ci,);

                    MEM(wi,);

                    vi = -vi;

                    sum = ;

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

                    {

                              sf("%d",&wi[i]);

                              sf("%lf",&ci[i]);

                              ci[i] = -ci[i];

                              sum+=wi[i];

                    }

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

                    {

                              zeroOnePack(wi[i],ci[i]);

                    }

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

                    {

                              if(dp[i]-vi>0.000000001)

                              {

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

                                        break;

                              }

                    }

          }

    return ;

}