//Δ_1004
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 111;
const int M = 1111;
const int inf = 1e9;
int n,m,a[N],b[N];
struct node{
    int f,g,r;
    node(int F=0,int G=0){
        f=F,g=G,r=0;
    }
}c[N][M],o;
bool operator<(node p,node q){
    if(p.f!=q.f)
        return p.f<q.f;
    if(p.g!=q.g)
        return p.g>q.g;
    return p.r<q.r;
}
bool operator==(node p,node q){
    return p.f==q.f&&p.g==q.g&&p.r==q.r;
}
void cmax(node&x,node y){
    if(x<y)
        x=y;
}
int e[N];
int chk(int i){
    int j,w;
    w=1;
    for(j=0;j<=m;j=j+1)    
        if(c[i][j]==o)
            w=0;
    if(w)
        return 0;
    o.f-=a[i],o.g-=i;
    return 1;
}
int main()
{
    int T,tc,i,j,x,y;
    cin>>T;
    for(tc=1;tc<=T;tc++){
        cin>>m>>n;
        for(i=1;i<=n;i=i+1)
            cin>>a[i]>>b[i];
        for(j=0;j<=m;j=j+1)
            c[n+1][j]=node(0,0);
        for(i=n;i>=1;i=i-1){
            for(j=0;j<=m;j=j+1)
                c[i][j]=c[i+1][j],c[i][j].r=0;
            for(j=b[i];j<=m;j=j+1){
                o=c[i+1][j-b[i]];
                o.f+=a[i],o.g+=i,o.r=1;
                cmax(c[i][j],o);
            }
        }
        o=node(-1,0);
        for(j=0;j<=m;j=j+1)
            cmax(o,c[1][j]);
        o.r=1;
        for(i=1;i<=n;i=i+1)
            e[i]=chk(i);
        x=0,y=0;
        for(i=1;i<=n;i=i+1)
            if(e[i])
                x+=a[i],y+=b[i];
        cout<<"Case #"<<tc<<':'<<endl;
        cout<<x<<' '<<y<<endl;
        j=0;
        for(i=1;i<=n;i=i+1)
            if(e[i])
                j=i;
        for(i=1;i<=n;i=i+1){
            if(e[i]){
                cout<<i;
                if(i!=j)
                    cout<<' ';
                else
                    cout<<endl;
            }
        }
    }
    return 0;
}