#include<bits/stdc++.h>
using namespace std;

const int N=105,M=1005,inf=0x3f3f3f3f;

struct node
{
    int s,n;
    string st;
}dp[M];

int m,n,s[N],c[N];

bool operator <(node a,node b)
{
    if(a.s!=b.s) return a.s<b.s;
    if(a.n!=b.n) return a.n>b.n;
    return a.st>b.st;
}

void solve(int cas)
{
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&s[i],&c[i]);
    for(int i=0;i<=m;i++) dp[i]=node{-inf,0,string("")};
    dp[0]=node{0,0,string("")};
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=c[i];j--)
        {
            node &now=dp[j-c[i]];
            node tmp=node{now.s+s[i],now.n+i,now.st+(char)i};
            if(dp[j]<tmp) dp[j]=tmp;
        }
    }
    int pos=0;
    for(int i=1;i<=m;i++)
        if(dp[pos]<dp[i]) pos=i;
    printf("Case #%d:\n",cas);
    printf("%d %d\n",dp[pos].s,pos);
    for(string::iterator it=dp[pos].st.begin();it!=dp[pos].st.end();it++)
    {
        if(it!=dp[pos].st.begin()) printf(" ");
        printf("%d",(int)*it);
    }
    if(dp[pos].n) puts("");
}

int main()
{
    //freopen("1004.in","r",stdin);
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
        solve(++cas);
    return 0;
}