//动态规划解决0/1背包问题同时递归打印所选的背包
#include<iostream>
#include<cstdio>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstring>
using namespace std;
int f[101][1002]= {0}; //f[i][j]为放i个背包容量为j的最大价值,并初始化为0
int n,w[101],W,v[101];
//n为背包个数，w[i]为第i个背包的体积，v[i]为第i个背包的价值，W为背包容量
int sta[120],top,ans;
void print(int i,int wt)
{
    if(i==1)
    {
        if(f[i][wt]) sta[top++]=1,ans+=w[1];
        return;
    }
    if(f[i][wt]>f[i-1][wt])
    {
        print(i-1,wt-w[i]);
        sta[top++]=i,ans+=w[i];//如果选了，则打印编号
    }
    else print(i-1,wt);

}
int main()
{
//    freopen("1.txt","r",stdin);
//    freopen("2.txt","w",stdout);
    int T,kase=0;
    scanf("%d",&T);
    while(T--)
    {
        memset(f,0,sizeof(f));
        top=ans=0;
        scanf("%d%d",&W,&n);
    for(int i=1; i<=n; i++)
    scanf("%d%d",v+i,w+i);
    for(int i=1; i<=n; i++)
        for(int j=0; j<=W; j++)
            if(j<w[i])
                f[i][j]=f[i-1][j];
            else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
    if(n)
    print(n,W);
    printf("Case #%d:\n%d %d\n",++kase,f[n][W],ans);
    if(0<top)
    printf("%d",sta[0]);
    for(int i=1;i<top;++i)
    printf(" %d",sta[i]);
    if(top>0)
    puts("");
    }
    return 0;
}