#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
bool vis[1001];
int _,n,m,w[101],c[101],f[1001],g[101][1001],as[101],tot,sum;
int main()
{
    int ca=0;
    scanf("%d",&_);
    while (_--)
    {
        scanf("%d",&m);
        scanf("%d",&n);
        int i,j;
        for (i=1;i<=n;i++)
            scanf("%d%d",&c[i],&w[i]);
        memset(vis,false,sizeof(vis));
        for (i=1;i<=n;i++)
        {
            if (c[i]==0)
                vis[i]=true;
        }
        int ans=0,od=99999999;
        while (true)
        {
            memset(f,0,sizeof(f));
            memset(g,0,sizeof(g));
            for (i=n;i>=1;i--) if (!vis[i])
            {
                if (w[i]==0)
                {

                }
                else
                {
                    for (j=m;j>=w[i];j--)
                        if (f[j-w[i]]+c[i]>f[j])
                        {
                            f[j]=f[j-w[i]]+c[i];
                            g[i][j]=true;
                        }
                        else
                            g[i][j]=false;
                }
            }
            int t=f[m];
            for (i=n;i>=1;i--)
                if (w[i]==0&&!vis[i])
                    t+=c[i];
            if (t<ans) break;
            ans=t;
            int mm=m,order=0,mini=0;
            for (i=1;i<=n;i++)
                if (g[i][mm])
                {
                    order+=i;
                    mm-=w[i];
                    if (i>mini) mini=i;
                }
            for (i=1;i<=n;i++)
                if (w[i]==0&&!vis[i])
                {
                    order+=i;
                }
            if (order>od)
            {
                if (mini>n||mini==0) break;
                vis[mini]=true;
                if (t==0) break;
                continue;
            }
            od=order;
            int M=m;
            tot=0,sum=0;
            for (i=1;i<=n;i++)
                if (g[i][M])
                {
                    as[++tot]=i;
                    M-=w[i];
                    sum+=w[i];
                }
            for (i=1;i<=n;i++)
                if (w[i]==0&&!vis[i])
                {
                    as[++tot]=i;
                }
            sort(as+1,as+tot+1);        
            if (mini>n||mini==0) break;
            vis[mini]=true;    
            if (t==0) break;
        }
        printf("Case #%d:\n",++ca);
        printf("%d %d\n",ans,sum);
        if (tot==0) {}
        else
        {
            for (i=1;i<tot;i++)
                printf("%d ",as[i]);
            printf("%d\n",as[tot]);
        }
    }
    return 0;
}