#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=102;
int dp[maxn][maxn*10],cost[maxn],score[maxn],path[maxn];
int ans,n,m,tot;
void print(int num,int sum)
{
    if(num==1)
    {
        if(dp[num][sum])
            path[++tot]=1,ans+=cost[1];
        return ;
    }
    if(dp[num][sum]>dp[num-1][sum])
    {
        print(num-1,sum-cost[num]);
        path[++tot]=num,ans+=cost[num];
    }
    else
        print(num-1,sum);
}
int main()
{
    int t,k=0;
    scanf("%d",&t);
    while(++k<=t)
    {
        tot=0,ans=0;
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&m,&n);
        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<=m; ++j)
                if(j>=cost[i])
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-cost[i]]+score[i]);
                else
                    dp[i][j]=dp[i-1][j];
        if(n)
            print(n,m);
        printf("Case #%d:\n%d %d\n",k,dp[n][m],ans);
        if(tot>0)
        {
            for(int i=1; i<tot; ++i)
                printf("%d ",path[i]);
            printf("%d\n",path[tot]);
        }
    }
    return 0;
}