/* ***********************************************
Author        :yang12138
Created Time  :2017年08月05日 星期六 21时29分28秒
File Name     :1004.cpp
************************************************ */
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <string>
#include <math.h>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef pair<int,int>pii;
#define lson (root<<1)
#define rson (root<<1|1)

const int N=105;
const int W=1005;
const int INF=1e9;
int dp[N][W],sum[N][W];
vector<int>p[N][W];
int s[N],c[N];

bool check(vector<int>&a,vector<int>&b){
    int len=min(a.size(),b.size());

    for(int i=0;i<len;i++){
        if(a[i]<b[i]) return 1;
        else if(a[i]>b[i]) return 0;
    }
    if(a.size()<b.size()) return 1;
    else return 0;
}

int t;
void solve(){

    int w,n;
    scanf("%d%d",&w,&n);

    for(int i=1;i<=n;i++) scanf("%d%d",s+i,c+i);


    for(int i=0;i<=n;i++){
        for(int j=0;j<=w;j++) dp[i][j]=-INF,sum[i][j]=INF;
    }
    dp[0][0]=sum[0][0]=0;

    for(int i=1;i<=n;i++){
        for(int j=w;j>=c[i];j--){
            dp[i][j]=dp[i-1][j-c[i]]+s[i];    
            sum[i][j]=sum[i-1][j-c[i]]+i;
            p[i][j]=p[i-1][j-c[i]];
            p[i][j].push_back(i);
        }
        for(int j=0;j<=w;j++){
            if(dp[i-1][j]>dp[i][j]){
                dp[i][j]=dp[i-1][j];
                sum[i][j]=sum[i-1][j];
                p[i][j]=p[i-1][j];
            }
            else if(dp[i-1][j]==dp[i][j]){
                if(sum[i-1][j]<sum[i][j]){
                    sum[i][j]=sum[i-1][j],p[i][j]=p[i-1][j];
                }
                else if(sum[i-1][j]==sum[i][j]){
                    if(check(p[i-1][j],p[i][j])) p[i][j]=p[i-1][j];
                }
            }
        }
        for(int j=0;j<=w;j++) p[i-1][j].clear();
    }

    int ans=0,tot=INF;

    for(int i=0;i<=w;i++){
        if(ans<dp[n][i]) ans=dp[n][i],tot=sum[n][i];
        else if(ans==dp[n][i] && sum[n][i]<tot) tot=sum[n][i];
    }
    //cerr<<ans<<' '<<tot<<endl;

    int sumcost=0;
    vector<int>pans;
    for(int i=0;i<=w;i++){
        if(dp[n][i]==ans && tot==sum[n][i]){
            if(pans.size()==0) pans=p[n][i],sumcost=i;
            else if(check(p[n][i],pans)) pans=p[n][i],sumcost=i;
        }
    }

    printf("Case #%d:\n",++t);
    printf("%d %d\n",ans,sumcost);
    if(pans.size()){
        printf("%d",pans[0]);
        for(int i=1;i<pans.size();i++) printf(" %d",pans[i]);
        printf("\n");
    }

    for(int j=0;j<=w;j++) p[n][j].clear();

}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int T;
    scanf("%d",&T);
    while(T--) solve();

    return 0;
}