#include <stdio.h>
#include <string.h>

#define MAXN 107
#define MAXM 1007

int c[MAXN], w[MAXN];
int f[MAXM];

struct Node {
  int i, nxt;
} node[MAXN*MAXM];
int nnodes, head[MAXM];
int que[MAXN], ql;

int main() {
  int t, n, m;
  scanf("%d", &t);
  for (int nt = 1; nt <= t; nt ++) {
    memset(f, 0, sizeof(f));
    memset(head, 0, sizeof(head));
    memset(node, 0, sizeof(node));
    nnodes = ql = 0;
    scanf("%d%d", &m, &n);

    for (int i = 1; i <= n; i++) scanf("%d%d", c+i, w+i);
    for (int i = 1; i <= n; i ++) {
      for (int j = m; j >= 0; j --) {
        if (j - w[i] >= 0 && f[j-w[i]] + c[i] > f[j]) {
          f[j] = f[j-w[i]] + c[i];
          node[++nnodes].i = i;
          node[nnodes].nxt = head[j-w[i]];
          head[j] = nnodes;
        }
        else {
        }
      }
    }
    int sum = 0;
    for (int i = head[m]; i; i = node[i].nxt) {
      sum += w[node[i].i];
      que[ql++] = node[i].i;
    }
    printf("Case #%d:\n%d %d\n", nt, f[m], sum);
    for (int i = ql-1; i >= 0; i --){
      if (i == 0) printf("%d\n", que[i]);
      else printf("%d ", que[i]);
    }
  }
  return 0;
}