#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define C 0.5772156649

#define ls l,m,rt<<1

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

#define pii pair<int,int>

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f3f;

double dp[N][maxn],gl[N];

int value[N];

int main()

{

    int res=,t;

    scanf("%d",&t);

    while(t--)

    {

        double p;

        int n;

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

        int sum=;

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

        {

            scanf("%d%lf",&value[i],&gl[i]);

            sum+=value[i];

        }

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

            for(int j=;j<=sum;j++)

                dp[i][j]=;

        dp[][]=;

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

        {

            for(int j=;j<=sum;j++)

            {

                if(j>=value[i])dp[i][j]=min(dp[i-][j],dp[i-][j-value[i]]+(-dp[i-][j-value[i]])*gl[i]);

                else dp[i][j]=dp[i-][j];

            }

        }

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

        {

            if(dp[n][i]<p)

            {

                printf("Case %d: %d\n",++res,i);

                break;

            }

        }

    }

    return ;

}

/********************

dp[i]抢到i元被抓概率不超过p

********************/