#include<bits/stdc++.h>
#define N 105
using namespace std;
struct data{
  int score,sum,id,ch;
  int operator < (const data &b)const{
    if (score!=b.score) return score>b.score;
    if (sum!=b.sum) return sum<b.sum;
    return id<b.id;
  }
}F[N][1005],tmp,ans;
int a[N],b[N],Ans[N];
int T,U,n,now,i,j,Case;
void upd(data &a,data b){
  if (b<a) a=b;
}
int main(){
  scanf("%d",&T);
  while (T--){
    scanf("%d%d",&U,&n);
    for (i=1;i<=n;i++)
      scanf("%d%d",&a[i],&b[i]);
    reverse(a+1,a+n+1);
    reverse(b+1,b+n+1);
    for (i=0;i<=n;i++) for (j=0;j<=U;j++) F[i][j].score=-1e9;
    F[0][0].score=0;
    for (i=0;i<n;i++)
      for (j=0;j<=U;j++)
        if (F[i][j].score>-1e9){
          tmp=F[i][j];tmp.ch=0;
          upd(F[i+1][j],tmp);
          tmp.score+=a[i+1];tmp.sum+=n-i;tmp.id=n-i;tmp.ch=1;
          if (j+b[i+1]<=U)
            upd(F[i+1][j+b[i+1]],tmp);
        }
    
    ans.score=-1e9;
    for (j=0;j<=U;j++)
      if (F[n][j]<ans)
        ans=F[n][j],now=j;
    //printf("%d %d %d %d\n",F[n][now].score,F[n-1][now].score,F[n][now].ch,F[n-1][now].ch);
    printf("Case #%d:\n",++Case);
    printf("%d %d\n",F[n][now].score,now);
    for (*Ans=0,i=n;i;i--)
      if (F[i][now].ch){
          Ans[++*Ans]=n-i+1,now-=b[i];
          //printf("%d\n",b[i]);
      }
    //if (!Ans[0]) puts("");
    //else 
      for (i=1;i<=*Ans;i++)
      printf("%d%c",Ans[i],i<Ans[0]?' ':'\n');
  }
}