#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const double eps = 1e-10;
const int maxn = 100000 + 100;
int n,m,T,c[104],d[105],cc=0;
int dp[1005][104],p[1005][104];
int path[1005][105];
int main() {
#ifdef ac
    freopen("in.txt" , "r" , stdin);
//    freopen("out.txt" , "w" , stdout);
#endif
    scanf("%d",&T);
    while(T--) {
        printf("Case #%d:\n",++cc);
        memset(dp,0,sizeof(dp));
        scanf("%d%d",&m,&n);
        for(int i=1;i<=n;++i) {
            scanf("%d%d",c+i,d+i);
        }
        for(int i=1;i<=n;++i){
            for(int j=0;j<=d[i];++j) {
                dp[j][i]=dp[j][i-1];
                p[j][i]=p[j][i-1];
                path[j][i]=0;
            }
            for(int j=d[i];j<=m;++j) {
                if(dp[j][i-1]<dp[j-d[i]][i-1]+c[i]) {
                    dp[j][i]=dp[j-d[i]][i-1]+c[i];
                    p[j][i]=p[j-d[i]][i-1]+i;
                    path[j][i]=1;
                }
                else if(dp[j][i]==dp[j-d[i]][i-1]+c[i]){
                    if(p[j-d[i]][i-1]+i<p[d[i]][i-1]) {
                        p[j][i]=p[j-d[i]][i-1]+i;
                        path[j][i]=1;
                    }
                }
                else {
                    dp[j][i]=dp[j][i-1];
                    p[j][i]=p[j][i-1];
                    path[j][i]=0;
                }
            }

        }

        vector<int> g;
        int x=m,y=n,ans=0,val=0;
        while(dp[x][y]) {
            if(path[x][y]){
                g.push_back(y);
                val+=d[y];
                x-=d[y];
            }
            y--;
        }
        if(!dp[m][n]) {
            printf("0 0\n");
            continue;
        }
        else {
            printf("%d %d\n",dp[m][n],val);
            reverse(g.begin(),g.end());
            for(int i=0;i<g.size();++i) {
                if(i)printf(" ");
                printf("%d",g[i]);
            }
            printf("\n");

        }
    }
    return 0;
}