#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;

int dp[110][1010],cost[110][1010],sumid[110][1010],pre[110][1010][110],n,b,score[110],val[110],num[110][1010];
int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&b,&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&score[i],&val[i]);
        
        for(int i=0;i<=b;i++)
            num[0][i]=dp[0][i]=cost[0][i]=sumid[0][i]=0;
            
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=b;j++)
            {
                dp[i][j]=dp[i-1][j];
                cost[i][j]=cost[i-1][j];
                sumid[i][j]=sumid[i-1][j];
                num[i][j]=num[i-1][j];
                for(int k=0;k<num[i][j];k++)
                    pre[i][j][k]=pre[i-1][j][k];
                if(j>0&&(dp[i][j-1]>dp[i][j]||(dp[i][j-1]==dp[i][j]&&sumid[i][j-1]<=sumid[i][j])))
                {
                    if(dp[i][j-1]==dp[i][j]&&sumid[i][j-1]==sumid[i][j])
                    {
                        //printf("Yes!!!\n");
                        bool flag=0;
                        for(int k=0;k<min(num[i][j-1],num[i][j]);k++)
                        {
                            if(pre[i][j-1][k]<pre[i][j][k])
                            {
                                flag=1;
                                break;
                            }
                            else if(pre[i][j][k]<pre[i][j-1][k])
                                break;
                        }
                        if(flag)
                        {
                            dp[i][j]=dp[i][j-1];
                            cost[i][j]=cost[i][j-1];
                            sumid[i][j]=sumid[i][j-1];
                            num[i][j]=num[i][j-1];
                            for(int k=0;k<num[i][j];k++)
                                pre[i][j][k]=pre[i][j-1][k];
                        }
                    }
                    else
                    {
                        dp[i][j]=dp[i][j-1];
                        cost[i][j]=cost[i][j-1];
                        sumid[i][j]=sumid[i][j-1];
                        num[i][j]=num[i][j-1];
                        for(int k=0;k<num[i][j];k++)
                            pre[i][j][k]=pre[i][j-1][k];
                    }
                    
                }
                if(j<val[i])
                    continue;
                if(dp[i-1][j-val[i]]+score[i]>dp[i][j]||(dp[i-1][j-val[i]]+score[i]==dp[i][j]&&sumid[i-1][j-val[i]]+i<=sumid[i][j]))
                {
                    if(dp[i-1][j-val[i]]+score[i]==dp[i][j]&&sumid[i-1][j-val[i]]+i==sumid[i][j])
                    {
                        bool flag=0;
                        pre[i-1][j-val[i]][num[i-1][j-val[i]]]=i;
                        for(int k=0;k<min(num[i-1][j-val[i]]+1,num[i][j]);k++)
                        {
                            if(pre[i-1][j-val[i]][k]<pre[i][j][k])
                            {
                                flag=1;
                                break;
                            }
                            else if(pre[i][j][k]<pre[i-1][j-val[i]][k])
                                break;
                        }
                        if(flag)
                        {
                            dp[i][j]=dp[i-1][j-val[i]]+score[i];
                            cost[i][j]=cost[i-1][j-val[i]]+val[i];
                            sumid[i][j]=sumid[i-1][j-val[i]]+i;
                            num[i][j]=num[i-1][j-val[i]]+1;
                            for(int k=0;k<num[i][j]-1;k++)
                                pre[i][j][k]=pre[i-1][j-val[i]][k];
                            pre[i][j][num[i][j]-1]=i;
                        }
                    }
                    else
                    {
                        dp[i][j]=dp[i-1][j-val[i]]+score[i];
                        cost[i][j]=cost[i-1][j-val[i]]+val[i];
                        sumid[i][j]=sumid[i-1][j-val[i]]+i;
                        num[i][j]=num[i-1][j-val[i]]+1;
                        for(int k=0;k<num[i][j]-1;k++)
                            pre[i][j][k]=pre[i-1][j-val[i]][k];
                        pre[i][j][num[i][j]-1]=i;
                    }
                }
            }
        }
        
        printf("Case #%d:\n%d %d\n",++cas,dp[n][b],cost[n][b]);
        if(num[n][b]>0)
            printf("%d",pre[n][b][0]);
        for(int i=1;i<num[n][b];i++)
            printf(" %d",pre[n][b][i]);
        if(num[n][b]>0)
        printf("\n");
    }
    return 0;
}