#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

double p,vol[],dp[];

int n,t,cost[];

int main(void)

{

    int i,j,sum;

    cin>>t;

    while(t--)

    {

        memset(dp,,sizeof(dp));

        sum=;

        dp[]=;

        cin>>p>>n;

        p=1.0-p;

        for(i=;i<n;i++) cin>>cost[i]>>vol[i],sum+=cost[i],vol[i]=1.0-vol[i];

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

        {

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

            dp[j]=max(dp[j],dp[j-cost[i]]*vol[i]);

        }

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

        {

            if(dp[i]>=p) break;

        }

        cout<<i<<endl;

    }

    return ;

}