#include<cstdio>
const int N=105,M=1005;
struct P{
  int x,y;//score sum
  P(){}
  P(int _x,int _y){x=_x,y=_y;}
  void operator+=(const P&b){
    if(x>b.x)return;
    if(x<b.x){x=b.x,y=b.y;return;}
    if(y>b.y)y=b.y;
  }
  P add(int a,int b){return P(x+a,y+b);}
}f[N][M],ans;
int Case,cas,n,m,i,j,V,a[N],b[N],q[N],cnt;
int main(){
  scanf("%d",&Case);
  for(cas=1;cas<=Case;cas++){
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);//score cost
    for(i=0;i<=m;i++)f[n+1][i]=P(-1000000000,0);
    f[n+1][0]=P(0,0);
    for(i=n;i;i--){
      for(j=0;j<=m;j++)f[i][j]=f[i+1][j];
      for(j=b[i];j<=m;j++)f[i][j]+=f[i+1][j-b[i]].add(a[i],i);
    }
    ans=P(0,0);
    for(j=0;j<=m;j++)ans+=f[1][j];
    for(j=0;j<=m;j++)if(f[1][j].x==ans.x&&f[1][j].y==ans.y)V=j;
    printf("Case #%d:\n%d %d\n",cas,ans.x,V);
    cnt=0;
    for(i=1;i<=n;i++){
      //can choose?
      if(V>=b[i]&&f[i+1][V-b[i]].x+a[i]==ans.x&&f[i+1][V-b[i]].y+i==ans.y){
        V-=b[i];
        ans.x-=a[i];
        ans.y-=i;
        q[++cnt]=i;
      }
    }
    for(i=1;i<=cnt;i++){
      printf("%d",q[i]);
      if(i<cnt)putchar(' ');
    }
    if(cnt)puts("");
  }
}