#include <bits/stdc++.h>
#define REP(i, x, n) for (int i = (x); i < (n); i++)
#define PER(i, x, n) for (int i = (n); i >= (x); i--)
#define endl "\n"
#define MAXN 1000000
#define MOD 1000000007
#define inf 10000000000000
typedef long long ll;
using namespace std;
ll B, N, ans, T, l;
int path[1005][1005];
int v[1005];
int f[1005];
int cost[1005];
vector<int> ansq;
vector<int> ansqq;
string s;
int main() {
    ios::sync_with_stdio(0);
    cin >> T;
    ans = 0;
    REP(t, 0, T) {
        ansq.clear();
        memset(path, 0, sizeof path);
        memset(f, 0, sizeof f);
        cin >> B >> N;
        REP(i, 0, N) {
            cin >> v[i] >> cost[i];
        }
        REP(i, 0, N) {
            PER(j, cost[i], B) {
                if (f[j] < f[j - cost[i]] + v[i]) {
                    f[j] = f[j - cost[i]] + v[i];
                    path[i][j] = 1;
                }
            }
        }
        ll maxx = -1;
        ll maxsc = 0, sumcost = 0;
        int jj = B;
        // REP(i, 0, B + 1) cout << f[i] << " ";
        for (int ii = N - 1; ii >= 0; ii--) {
            if (path[ii][jj]) {
                ansq.push_back(ii + 1);
                jj -= cost[ii];
                sumcost += cost[ii];
            }
        }
        cout << "Case #" << t + 1 << ":" << endl;
        cout << f[B] << " " << sumcost << endl;
        if (!ansq.empty()) {
            sort(ansq.begin(), ansq.end());
            REP(i, 0, ansq.size() - 1) {
                cout << ansq[i] << " ";
            }
            if (!ansq.empty()) {
                cout << ansq[ansq.size() - 1];
            }
            cout << endl;
        }
    }
    return 0;
}