#include<stdio.h>
#define MAXB 1005
#define MAXN 105
typedef long long U64;
int C[MAXN],S[MAXN];
int F[MAXN][MAXB],from[MAXN][MAXB];
void work(int b,int n)
{
    int i,j;
    for(i=0;i<=b;i++)
    {
        F[0][i]=0;
        from[0][i]=-1;
    }
    for(i=1;i<=n;i++)
    {
        F[i][0]=0;
        from[i][0]=-1;
        for(j=0;j<=b;j++)
        {
            F[i][j]=F[i-1][j];
            from[i][j]=from[i-1][j];
            if(C[i]>j)continue;
            int g=S[i]+F[i-1][j-C[i]];
            if(g>F[i-1][j])
            {
                F[i][j]=g;
                from[i][j]=i;
            }
        }
    }
}
int res_array[105],res_cnt=0,res_cost=0;
void get_res(int b,int n)
{
    res_cnt=0;
    res_cost=0;
    while(from[n][b]!=-1)
    {
        if(n<1||b<0)((int *)0)[0]=1;
        int i=from[n][b];
        res_array[res_cnt++]=i;
        b-=C[i];
        res_cost+=C[i];
        n=i-1;
    }
}
int main()
{
    int i,b,n,t,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&b,&n);
        if(b>1000||b<0||n>100||n<0)while(1);
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",S+i,C+i);
            if(S[i]>1000||S[i]<0||C[i]>1000||C[i]<0)while(1);
            S[i]=S[i]*10000-i;
        }
        work(b,n);
        get_res(b,n);
        printf("Case #%d:\n",++cas);
        printf("%d %d\n",(F[n][b]+9999)/10000,res_cost);
        if(res_cnt>0)
        {
            for(i=res_cnt-1;i>0;i--)printf("%d ",res_array[i]);
            printf("%d\n",res_array[0]);
        }
    }
    return 0;
}