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

struct food {
    int score, cost;
};

struct data {
    int s;
    vector<int> f;
    int sum;
    data() { }
    data(int score) : s(score) {
        
    }
};

/*
1
10 4
3 3
4 4
6 6
3 3
*/

int main() {
    int t, tt = 0;
    cin >> t;
    while (t--) {
        int b, n;
        cin >> b >> n;
        vector<food> a(n+1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i].score >> a[i].cost;
        }
        const int inf = 1e9;
        vector<data> dp(b+1, data(-inf));
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            int s = a[i].score, c = a[i].cost;
            for (int j = b; j >= c; j--) {
                if ((dp[j].s < dp[j-c].s + s) || (
                    (dp[j].s == dp[j-c].s + s) && (dp[j-c].sum + i < dp[j].sum))) {
                    dp[j].s = dp[j-c].s + s;
                    dp[j].f = dp[j-c].f;
                    dp[j].sum = dp[j-c].sum + i;
                    dp[j].f.push_back(i);
                }
            }
        }
        int score = 0, cost = 0, minSum = inf;
        vector<int> res;
        for (int i = b; i >= 0; i--) {
            if (dp[i].s > score || (dp[i].s == score && dp[i].sum < minSum)) {
                score = dp[i].s; cost = i;
                minSum = dp[i].sum;
            }
        }
        cout << "Case #" << ++tt << ":" << endl;
        cout << score << " " << cost << endl;
        if (score != 0) {
            res = dp[cost].f;
            for (int i = 0; i < res.size(); i++) {
                if (i != 0) cout << " ";
                cout << res[i];
            }
            cout << endl;
        }
    }
}