#include <bits/stdc++.h>
  using namespace std;
 const int maxn = 110;
const int maxm = 1010;
  int m, n;
 int v[maxn], w[maxn];
  int f[maxm];
 int path[maxn][maxm];
 vector<int> tmp;
 
 int main() {
    
     int T;
    scanf("%d", &T);
    for (int q = 1; q <= T;q++)
    {
        memset(path, 0, sizeof(path));
        memset(f, 0, sizeof(f));
        tmp.clear();
        scanf("%d%d",&m,&n);
         for(int i = 1; i <= n; i++) {
            scanf("%d%d",&v[i], &w[i]);
        }
        for(int i = 1; i <= n; i++) {
            for(int j = m; j >= w[i]; j--) {
                 if(f[j] < f[j-w[i]]+v[i]) {
                   f[j] = f[j-w[i]] + v[i];
                    path[i][j] = 1;
                 }
            }
        }
         printf("Case #%d:\n", q);
        int tot1 = 0, tot2 = 0;
         for(int i = n, j = m; i >= 1; i--) {
             if(path[i][j]) {
               tot1 += v[i]; tot2 += w[i];
                tmp.push_back(i);
                 j -= w[i];
          }
         }
        printf("%d %d\n", tot1, tot2);
        sort(tmp.begin(), tmp.end());
         for(int i = 0; i < tmp.size(); i++) {
            printf("%d%c", tmp[i], i==tmp.size()-1?'\n':' ');
        }
    }
    return 0;
}