#include<bits/stdc++.h>
using namespace std;
int value[105];
int cost[105];
int dp[1005];
int n,m;
vector<int> vec[1005];
int sum[1005];
int main(){
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            vec[i].clear();
            sum[i]=0;
        }
        for(int i=1;i<=m;i++){
            scanf("%d%d",&value[i],&cost[i]);
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=m;i++){
            for(int j=n;j>=0;j--){
                if(j>=cost[i]){
                    if(dp[j]<dp[j-cost[i]]+value[i]){
                        vec[j]=vec[j-cost[i]];
                        vec[j].push_back(i);
                        sum[j]=sum[j-cost[i]];
                        sum[j]+=i;
                        dp[j]=dp[j-cost[i]]+value[i];
                    }
                    else if(dp[j]==dp[j-cost[i]]+value[i]){
                        if(sum[j]>sum[j-cost[i]]+i){
                            sum[j]=sum[j-cost[i]];
                            sum[j]+=i;
                        }
                    }
                }
            }
        }
        printf("Case #%d:\n",cas);
        int ans=0;
        for(int i=0;i<vec[n].size();i++){
            ans+=cost[vec[n][i]];
        }
        printf("%d %d\n",dp[n],ans);
        int flag=0;
        for(int i=0;i<vec[n].size();i++){
            flag=1;
            printf(i==0?"%d":" %d",vec[n][i]);
        }
        if(flag){
            printf("\n");
        }
    }
    return 0;
}