#include <bits/stdc++.h>
using namespace std;
int a[305][1200],c[305],d[305][2];
int cent;

int dfs(int x,int y)
{
    if(x<=0||y<0)
        return 0;
    int s=a[x][y];
    while(s==a[x-1][y]){
        if(s==a[x-1][y]&&x>0)
            x--;
        if(x<=0||y<0)
            break;
    }
    if(x<=0)
        return 0;
    dfs(x-1,y-d[x][1]);
    c[cent++]=x;
    return 0;
}

int main()
{
    int t,n,mon;
    cin>>t;
    for(int num=1;num<=t;num++){
        memset(a,0,sizeof(a));
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        cent=0;
        cin>>mon>>n;
        for(int i=1;i<=n;i++){
            int x,y;
            cin>>x>>y;
            d[i][0]=x,d[i][1]=y;
            for(int j=0;j<=mon;j++)
            {
                if(j>=y)
                {
                    a[i][j]=max(a[i-1][j], a[i-1][j-y]+x);    
                }    
                else
                    a[i][j]=a[i-1][j];
            }
        }
        dfs(n,mon);
        int ans1=0,ans2=0;
        for(int i=0;i<cent;i++)
        {
            ans1+=d[c[i]][0];
            ans2+=d[c[i]][1];
        }
        printf("Case #%d:\n%d %d\n",num,ans1,ans2);
        for(int i=0;i<cent;i++)
            if(i==0)
                cout<<c[i];
            else
                cout<<" "<<c[i];
        if(cent!=0)cout<<endl;
    }
    return 0;
}