#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define maxn 100
#define maxm 10000
#define maxscore 10001

struct node
{
    long g;
    long num[maxn+1];
}iden[maxm+1];

long score[maxn+1],cost[maxn+1];
long f[maxm+1],total[maxm+1];

long max(long a,long b)
{
    if (a>b)
        return a;
    else
        return b;
}

long min(long a,long b)
{
    if (a>b)
        return b;
    else
        return a;
}

bool pan(long j,long k)
{
    long l;
    for (l=1;l<iden[j].g;l++)
        if (iden[j].num[l]<iden[k].num[l])
            return true;
        else
            return false;
    return false;
}

int main()
{
    long t,planprice,n;
    long i,j,k,l,ca,sum;
    scanf("%ld",&t);
    for (ca=1;ca<=t;ca++)
    {
        scanf("%ld",&planprice);
        scanf("%ld",&n);
        for (i=1;i<=n;i++)
            scanf("%ld%ld",&score[i],&cost[i]);

        sum=0;
        f[0]=0;
        iden[0].g=0;
        for (i=1;i<=maxm;i++)
            f[i]=-1;

        for (i=1;i<=n;i++)
        {
            sum+=cost[i];
            for (j=min(sum,planprice),k=j-cost[i];j>=cost[i];j--,k--)
                if (f[k]!=-1 && (f[k]+score[i]>f[j] || (f[k]+score[i]==f[j] && total[k]+i<total[j])
                    || (f[k]+score[i]==f[j] && total[k]+i==total[j] && pan(k,j))))
                {
                    f[j]=f[k]+score[i];
                    total[j]=total[k]+i;
                    iden[j].g=iden[k].g+1;
                    for (l=1;l<=iden[k].g;l++)
                        iden[j].num[l]=iden[k].num[l];
                    iden[j].num[iden[j].g]=i;
                }
        }

        j=planprice;
        for (i=planprice;i>=0;i--)
            if (f[i]>f[j] || (f[i]==f[j] && total[i]<total[j]) || (f[i]==f[j] && total[i]==total[j] && pan(i,j)))
                j=i;
        printf("Case #%ld:\n",ca);
        printf("%ld %ld\n",f[j],j);
        for (i=1;i<iden[j].g;i++)
            printf("%ld ",iden[j].num[i]);
        if (iden[j].g!=0)
            printf("%ld\n",iden[j].num[i]);
    }
    return 0;
}