#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const INF = 0x7fffffff;
int dp[1005], s[105], c[105];
int N, B;
 
struct DATA {
    int n, id[105], sum;
}d[1005];
 
int main() {
    int T;
    scanf("%d", &T);
    for (int ca = 1; ca <= T; ca ++) {
        printf("Case #%d:\n", ca);
        scanf("%d %d", &B, &N);
        for (int i = 1; i <= N; i ++) {
            scanf("%d %d", &s[i], &c[i]);
        }
        memset(d, 0, sizeof(d));
        for (int i = 0; i <= B; i ++) {
                dp[i] = -INF;
        }
        dp[0] = 0;
        for (int i = 1; i <= N; i ++) {
            for (int j = B; j >= c[i]; j --) {
                if (dp[j] < dp[j - c[i]] + s[i] || (dp[j] == dp[j - c[i]] + s[i] && d[j].sum > i)) {
                    dp[j] = dp[j - c[i]] + s[i];
                    d[j] = d[j - c[i]];
                    d[j].id[d[j].n ++] = i;
                    d[j].sum += i;
                }
            }
        }
        int maxS = -INF, maxC, curMin = INF;
        for (int i = B; i >= 0; i--) {
            //printf("maxS = %d dp[%d] = %d\n", maxS, i, dp[i]);
            if (maxS < dp[i] || (maxS == dp[i] && curMin > d[i].sum)) {
                maxS = dp[i];
                maxC = i;
                curMin = d[i].sum;
            }
        }
        printf("%d %d\n", maxS, maxC);
        int sz = d[maxC].n;
        if (sz > 0) {
            for (int i = 0; i < sz - 1; i ++){
                printf("%d ", d[maxC].id[i]);
            }
            printf("%d\n", d[maxC].id[sz - 1]);
        }
    }
}