#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

void solve(int cas) {
    int B, n;
    scanf("%d%d", &B, &n);
    vector<int> score(n), cost(n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &score[i], &cost[i]);
        score[i] = score[i] * 10000 - (i + 1);
    }

    vector<vector<int>> dp(n+1, vector<int>(B+1, 0));
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = dp[i+1];
        for (int j = B; j >= cost[i]; j--) {
            dp[i][j] = max(dp[i][j], dp[i+1][j-cost[i]] + score[i]);
        }
    }

    vector<int> ans;
    int left = B, sum = 0;
    for (int i = 0; i < n; i++) {
        if (left >= cost[i] && score[i] + dp[i+1][left-cost[i]] == dp[i][left]) {
            left -= cost[i];
            sum += score[i] / 10000 + 1;
            ans.push_back(i+1);
        }
    }
    printf("Case #%d:\n%d %d\n", cas, sum, B - left);
    /*
    if (ans.size()) printf("%d", ans[0]);
    for (int i = 1; i < ans.size(); i++) printf(" %d", ans[i]);
    */
    if (ans.size()) {
        printf("%d", ans[0]);
        for (int i = 1; i < ans.size(); i++) printf(" %d", ans[i]);
        printf("\n");
    }
}

int main() {
    int T = 1, t = 0;
    scanf("%d", &T);
    while (T--) solve(++t);
    return 0;
}