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

const int N = 1000 + 10;
const int M = 100 + 10;
int t, b, n, s[M], c[M];
int dp[N], vis[N][M], kcase=0;

int main()
{
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &b, &n);
        for (int i = 1; i <= n; ++ i) scanf("%d%d", &s[i], &c[i]);
        memset(dp, 0, sizeof(dp));
        memset(vis, 0, sizeof(vis));
        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];
                    vis[j][i] = 1;
                }
            }
        }
        int sum = 0;
        vector<int> rc;
        for (int i = n, j = b; i >= 1; -- i) {
            if (vis[j][i]) {
                rc.push_back(i);
                sum += c[i];
                j -= c[i];
            }
        }
        printf("Case #%d:\n", ++kcase);
        printf("%d %d\n", dp[b], sum);
        if (rc.size() == 0) continue;
        else {
            sort(rc.begin(), rc.end());
            printf("%d", rc[0]);
            for (int i = 1; i < rc.size(); ++ i) printf(" %d", rc[i]);printf("\n");
        }
    }
    return 0;
}