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

const int maxn=110,maxm=1010;
int t,b,n;
int dp[maxn][maxm],d[maxn][maxm],c[maxn][maxm];
int comp[2][maxn],num[2],spend[2],cost[maxn],score[maxn];
void recover(int i,int j,int s)
{
    spend[i]=num[i]=0;
    for(int k=j;k>=0;k--){
        if(c[k][s]){
            comp[i][num[i]++]=k;
            s-=cost[k];
            spend[i]+=cost[k];
        }
    }
    reverse(comp[i],comp[i]+num[i]);
}
int compare(){
    int i=0;
    for(;i<num[0]&&i<num[1];i++){
        if(comp[0][i]==comp[1][i])continue;
        return comp[0][i]-comp[1][i];
    }
    if(i<num[0])return -1;
    if(i<num[1])return 1;
    return 0;
}

int main(){
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++){
        scanf("%d%d",&b,&n);
        memset(dp,0,sizeof(dp));
        memset(d,0,sizeof(d));
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++)scanf("%d%d",score+i,cost+i);
        for(int i=1;i<=n;i++){
            for(int j=0;j<=b;j++){
                //默认先不选择i 
                dp[i][j]=dp[i-1][j];
                d[i][j]=d[i-1][j];
                if(cost[i]<=j){
                    
                    int tmp1=dp[i-1][j-cost[i]]+score[i],tmp2=d[i-1][j-cost[i]]+i;
                    if(tmp1>dp[i][j]){
                        dp[i][j]=tmp1;
                        d[i][j]=tmp2;
                        c[i][j]=1;
                    }else if(tmp1==dp[i][j]){
                        if(tmp2<d[i-1][j]){
                            d[i][j]=tmp2;
                            c[i][j]=1;
                        }else if(tmp2==d[i-1][j]){
                            d[i][j]=tmp2;
                            c[i][j]=1;
                            recover(0,i,j);
                            recover(1,i-1,j);
                            if(compare()>0){
                                c[i][j]=0;
                            }    
                        }
                    }
//                    printf("%d %d %d\n",i,j,dp[i][j]);    
                }
                
            }
        }
        printf("Case #%d:\n",kase);
        recover(0,n,b);
        printf("%d %d\n",dp[n][b],spend[0]);
        for(int i=0;i<num[0];i++){
            printf("%d",comp[0][i]);
            if(i!=num[0]-1){
                printf(" ");
            }
        }
        if(num[0]!=0)
        printf("\n");
    }
    
    return 0;
}