#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define inf (1<<30)
using namespace std;
struct data{
    int scor,sumd,id;
    void clear()
    {
        scor = -inf;
        sumd = inf;
    }
}f[110][1010];
int T,mx,n,sc[110],cs[110],last,cost,f1,f2;
void Read()
{
    scanf("%d",&mx);
    scanf("%d",&n);
    for (int i = 1;i<=n;++i) scanf("%d%d",&sc[i],&cs[i]);
    for (int i = 0;i<=n+1;++i) 
     for (int j = 0;j<=mx;++j)
      f[i][j].clear();
     f[n+1][0].scor = f[n+1][0].sumd = 0; 
}
bool better(int x,int y)
{
    if (f[1][x].scor != f[1][y].scor) return f[1][x].scor > f[1][y].scor;
    if (f[1][x].sumd != f[1][y].sumd) return f[1][x].sumd < f[1][y].sumd;
    f1 = f[1][x].id;f2 = f[1][y].id;
    while (f1 && f2)
    {
        if (f1!=f2) return f1<f2;
        x-=cs[f1];y-=cs[f1];
        f1 = f[f1 + 1][x].id;
        f2 = f[f2 + 1][y].id; 
    }
}
void Out()
{
    cost = 0;
    for (int i = 1;i<=mx;++i) if (better(i,cost)) cost = i;
    printf("%d %d\n",f[1][cost].scor,cost);
    last = f[1][cost].id;
    while (last)
    {
        printf("%d",last);
        cost -= cs[last];
        last = f[last + 1][cost].id;
        putchar(last ? ' ':'\n');    
    }
}
bool cmp(data a,data b,int x)
{
    if (a.scor != b.scor + sc[x]) return a.scor < b.scor + sc[x];
    if (a.sumd != b.sumd + x) return a.sumd > b.sumd + x;
}
void Done()
{
    for (int i = n;i>=1;--i)
        for (int j = 0;j<=mx;++j)
        {
            f[i][j] = f[i+1][j];
            if (j>=cs[i] && cmp(f[i][j],f[i+1][j-cs[i]],i))
            {
                f[i][j] = f[i+1][j-cs[i]];
                f[i][j].sumd+=i;
                f[i][j].scor+=sc[i];
                f[i][j].id = i;
            }
        }
}
int main()
{
    scanf("%d",&T);
    for (int i = 1;i<=T;++i)
    {
        Read();
        Done();
        printf("Case #%d:\n",i);
        Out();
    }        
    fclose(stdin);
    fclose(stdout);
}