#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
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;

signed main() {
    // freopen("in", "r", stdin);
    int T, _ = 1;
    scanf("%d", &T);
    while(T--) {
        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", _++);
        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;
}