1
#include<bits/stdc++.h>
2
using namespace std;
3
int v[105],n,t;
4
double w[105],dp[10010],W;
5
int main()
6
{
7
    cin>>t;
8
    while(t--)
9
    {
10
        cin>>W>>n;
11
        W=1-W;
12
        int ans=0;
13
        for(int i=0;i<n;i++)
14
        {
15
            cin>>v[i]>>w[i];
16
            w[i]=1-w[i];
17
            ans+=v[i];
18
        }
19
        memset(dp,0,sizeof(dp));
20
        dp[0]=1;
21
        for(int i=0;i<n;i++)
22
        {
23
            for(int j=ans;j>=v[i];j--)
24
            {
25
                dp[j]=max(dp[j],dp[j-v[i]]*w[i]);
26
            }
27
        }
28
        if(W==1) // 输入的 W 为 0时，dp[0] == W ，无输出 ， 需要特判  
29
        	cout << 0 <<"\n";
30
        for(int i=ans;i>=0;i--)
31
        {
32
            if(dp[i]>W){
33
                cout<<i<<"\n";
34
                break;
35
            }
36
        }
37
    }
38
    return 0;
39
}