#include<bits/stdc++.h>
using namespace std;
int t,n,m,N,i,j,a[105],b[105],f[105][1005],g[105][1005],ans[105];
int main()
{
    scanf("%d",&t);
    for(int x=1;x<=t;x++)
    {
        printf("Case #%d:\n",x);
        scanf("%d%d",&m,&n);
        for(i=1;i<=n;i++)scanf("%d%d",a+i,b+i);
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for(i=n;i;i--)for(j=0;j<=m;j++)
        {
            f[i][j]=f[i+1][j];
            g[i][j]=g[i+1][j];
            if(j>=b[i]&&(f[i][j]<f[i+1][j-b[i]]+a[i]||f[i][j]==f[i+1][j-b[i]]+a[i]&&g[i][j]>g[i+1][j-b[i]]+i))
            {
                f[i][j]=f[i+1][j-b[i]]+a[i];
                g[i][j]=g[i+1][j-b[i]]+i;
            }
        }
        cout<<f[1][m]<<' ';
        for(N=0,i=1,j=m;i<=n;i++)if(j>=b[i]&&f[i][j]==f[i+1][j-b[i]]+a[i]&&g[i][j]==g[i+1][j-b[i]]+i)
        {
            ans[++N]=i;
            j-=b[i];
        }
        cout<<m-j;
        if(N)
        {
            cout<<endl;
            for(i=1;i<N;i++)cout<<ans[i]<<' ';
            cout<<ans[i];
        }
        cout<<endl;
    }
    return 0;
}