#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #define lson l, m, rt<<1

 #define rson m+1, r, rt<<1|1

 #define IO ios::sync_with_stdio(false);cin.tie(0);

 #define INF 1e9

 typedef long long ll;

 using namespace std;

 int t, n, m[];

 double P, p[], dp[];

 int main()

 {

     IO;

     cin >> t;

     while(t--){

         cin >> P >> n;

         int sum = ;

         memset(dp, , sizeof(dp));

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

             cin >> m[i] >> p[i];

             sum += m[i];

         }

         dp[] = ;//只要dp[0]=1即可，不是全置1

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

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

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

             }

         }

         int maxm=-INF;

         for(int i = ; i <= sum; i++){

             if(-dp[i] <= P){

                 maxm = max(i, maxm);//用max界定最大值最方便

             }

         }

         cout << maxm << endl;

     }

     return ;

 }