#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <ctime>
#include <cmath>
#define ll long long
#define maxn 100020
using namespace std;


int f[1020];//cost
int g[1020];//seq_sum;
int pre[102][1020];
int last[1020];
int n,T,B;
int a[102],b[102];
int dl[1020],top;
int ans1,ans2,ans3;

void try_update(int j,int i){
  f[j] = f[j-b[i]]+a[i];
  pre[i][j] = last[j-b[i]];
  last[j] = i;
  g[j] = g[j-b[i]]+i;

  if(f[j] > ans1){
    ans1 = f[j];
    ans2 = g[j];
    ans3 = j;
  }else if(f[j]==ans1 && g[j] < ans2){
    ans1 = f[j];
    ans2 = g[j];
    ans3 = j;
  }
}

void get_ans(int ans1,int ans3){
  if(ans1 == 0){
    printf("0 0\n");
    return;
  }

  top = 0;
  int now = last[ans3];
  while(now){
    dl[++top] = now;
    ans3 = ans3 - b[now];
    now = pre[now][ans3 + b[now]];
  }

  int co = 0;
  for(int i=1;i<=top;++i)co+=b[dl[i]];
  printf("%d %d\n",ans1,co);
  printf("%d",dl[top]);
  for(int i=top-1;i;--i)printf(" %d",dl[i]);
  printf("\n");
}

int main()
{

  scanf("%d",&T);


  for(int ii=1;ii<=T;++ii){

    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    memset(pre,0,sizeof(pre));
    memset(last,0,sizeof(last));
    ans1 = ans2 = 0;
    scanf("%d%d",&B,&n);
    for(int i=1;i<=n;++i){
      scanf("%d%d",&a[i],&b[i]);

      for(int j=B;j>=0;--j){
        if(j < b[i])break;
        if(f[j-b[i]]+a[i] > f[j])try_update(j,i);
        else if(f[j-b[i]]+a[i] == f[j] && g[j-b[i]] + i < g[j])try_update(j,i);
      }
    }

    printf("Case #%d:\n",ii);
    get_ans(ans1,ans3);
  }
  return 0;
}