#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct dat {
    int a;
    vector<int> b;

    dat(int aa = -1) : a(aa) {}
};

bool operator<(dat lhs, dat rhs) {
    if (rhs.a > lhs.a) {
        return true;
    } else if (lhs.a > rhs.a) {
        return false;
    }
    int s = accumulate(lhs.b.begin(), lhs.b.end(), 0);
    int t = accumulate(rhs.b.begin(), rhs.b.end(), 0);
    if (s > t) {
        return true;
    } else if (s < t) {
        return false;
    }
    return lhs.b > rhs.b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin >> tt;
    for (int qq = 1; qq <= tt; qq++) {
        int b, n;
        cin >> b >> n;
        vector<int> s(n), c(n);
        for (int i = 0; i < n; i++) {
            cin >> s[i] >> c[i];
        }
        vector<vector<dat>> dp(n + 1, vector<dat>(b + 1));
        dp[0][0].a = 0;
        for (int i = 0; i < n; i++) {
            dp[i + 1] = dp[i];
            for (int j = 0; j + c[i] <= b; j++) {
                auto p = dp[i][j];
                if (p.a == -1) {
                    continue;
                }
                p.a += s[i];
                p.b.emplace_back(i + 1);
                dp[i + 1][j + c[i]] = max(dp[i + 1][j + c[i]], p);
            }
        }
        auto ans = dp[0][0];
        int cc = 0;
        for (int i = 0; i <= b; i++) {
            if (ans < dp[n][i]) {
                ans = dp[n][i];
                cc = i;
            }
        }
        cout << "Case #" << qq << ":\n";
        cout << ans.a << " " << cc << '\n';
        if (!ans.b.empty()) {
            for (int i = 0; i < (int) ans.b.size(); i++) {
                if (i > 0) {
                    cout << " ";
                }
                cout << ans.b[i];
            }
            cout << '\n';
        }
    }
    return 0;
}