#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 100+5
#define MAXB 1000+5
int B,N,ansScore,ansCost;
bool visit[MAXN];
int score[MAXN],cost[MAXN];
int dp[MAXN][MAXB];
void solve()
{
    memset(dp,0,sizeof(dp));
    ansCost=0;
    for(int i=1;i<=N;i++)
    {
        for(int r=0;r<=B;r++)
        {
            if(r<cost[i])
            {
                dp[i][r]=dp[i-1][r];
            }
            else
            {
                dp[i][r]=max(dp[i-1][r],dp[i-1][r-cost[i]]+score[i]);
            }
        }
    }
    int r=B;
    for(int i=N;i>0;i--)
    {
        if(dp[i][r]>dp[i-1][r])
        {
            visit[i]=1;
            ansCost+=cost[i];
            r=r-cost[i];
        }
        else
        {
            visit[i]=0;
        }
    }
    ansScore=dp[N][B];
}
int main()
{
    //freopen("Test.txt","r",stdin);
    int t,cnt=1;
    scanf("%d",&t);
    while(t--)
    {
        int flag=false;
        scanf("%d",&B);
        scanf("%d",&N);
        if(N==0) flag=true;
        for(int i=1;i<=N;i++)
        {
            scanf("%d %d",&score[i],&cost[i]);
        }
        if(!flag) solve();
        printf("Case #%d:\n",cnt++);
        if(flag || ansScore==0 && ansCost==0)
        {
            printf("%d %d\n",0,0);
        }
        else
        {
            printf("%d %d\n",ansScore,ansCost);
            bool f=false;
            for(int i=1;i<=N;i++)
            {
                if(visit[i])
                {
                    if(!f)
                    {
                        f=true;
                        printf("%d",i);
                    }
                    else
                    {
                        printf(" %d",i);
                    }
                }

            }
            printf("\n");
        }
    }
    return 0;
}