#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
int T,cas,b,n,v[105],w[105],dp[105][1005],sum[105][1005],last[105][1005];
vector<int> res;
int main()
{
    scanf("%d",&T);
    for (int cas=1;cas<=T;++cas) {
        scanf("%d%d",&b,&n);
        for (int i=1;i<=n;++i)
            scanf("%d%d",&v[i],&w[i]);
        memset(dp,0xcf,sizeof dp);
        memset(sum,0x3f,sizeof sum);
        memset(last,0,sizeof last);
        dp[0][0]=sum[0][0]=0;
        for (int i=1;i<=n;++i)
            for (int j=0;j<=b;++j) {
                dp[i][j]=dp[i-1][j];
                sum[i][j]=sum[i-1][j];
                last[i][j]=j;
                if (j>=w[i]) {
                    if (dp[i][j]<dp[i-1][j-w[i]]+v[i]) {
                        dp[i][j]=dp[i-1][j-w[i]]+v[i];
                        sum[i][j]=sum[i-1][j-w[i]]+i;
                        last[i][j]=j-w[i];
                    } else if (dp[i][j]==dp[i-1][j-w[i]]+v[i]) {
                        if (sum[i][j]>sum[i-1][j-w[i]]+i) {
                            sum[i][j]=sum[i-1][j-w[i]]+i;
                            last[i][j]=j-w[i];
                        }
                    }
                }
            }
        int maxv=0,mino=inf,resx=0,resy=0;
        for (int i=0;i<=b;++i)
            if (dp[n][i]>maxv) {
                maxv=dp[n][i];
                mino=sum[n][i];
                resx=n,resy=i;
            } else if (dp[n][i]==maxv&&sum[n][i]<=mino) {
                mino=sum[n][i];
                resx=n,resy=i;
            }
        printf("Case #%d:\n%d %d\n",cas,maxv,resy);
        res.clear();
        while (resx) {
            if (last[resx][resy]!=resy||(w[resx]==0&&v[resx]!=0))
                res.push_back(resx);
            resy=last[resx][resy];
            --resx;
        }
        for (int i=res.size()-1;i>=0;--i)
            printf("%d%c",res[i],!i?'\n':' ');
    }
    return 0;
}