#include <bits/stdc++.h>

const int maxn = 200;
const int maxb = 2000;
int s[maxn], c[maxn];
const int inf = 1e9 + 7;

struct Node {
  int score, sum;
  std::vector<int> choice;
  Node(): score(0), sum(0) {
    choice.clear();
  }
  Node(int score): score(score), sum(0) {
    choice.clear();
  }
  Node add(int i) {
    Node ret = *this;
    ret.score += s[i];
    ret.sum += i;
    ret.choice.push_back(i);
    return ret;
  }
  friend bool operator<(const Node &a, const Node &b) {
    if (a.score < b.score) {
      return true;
    }
    if (a.score > b.score) {
      return false;
    }
    if (a.sum > b.sum) {
      return true;
    }
    if (a.sum < b.sum) {
      return false;
    }
    for (int i = 0, len = std::min(a.choice.size(), b.choice.size()); i < len; ++i) {
      if (a.choice[i] > b.choice[i]) {
        return true;
      }
      if (a.choice[i] < b.choice[i]) {
        return false;
      }
    }
    return false;
  }
} dp[maxb];

int main() {
  int test, b, n;
  std::cin >> test;
  for (int ca = 1; ca <= test; ++ca) {
    std::cin >> b >> n;
    for (int i = 1; i <= n; ++i) {
      std::cin >> s[i] >> c[i];
    }
    for (int i = 1; i <= b; ++i) {
      dp[i] = Node(-inf);
    }
    dp[0] = Node();
    for (int i = 1; i <= n; ++i) {
      for (int j = b; j >= c[i]; --j) {
        dp[j] = std::max(dp[j], dp[j - c[i]].add(i));
      }
    }
    int ans = 0;
    for (int i = 1; i <= b; ++i) {
      if (dp[ans] < dp[i]) {
        ans = i;
      }
    }
    std::cout << "Case #" << ca << ":" << std::endl << dp[ans].score << " " << ans << std::endl;
    for (int i = 0, sz = dp[ans].choice.size(); i < sz; ++i) {
      std::cout << dp[ans].choice[i] << (i + 1 == sz? "\n": " ");
    }
  }
  return 0;
}