#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;


long long B, N;
long long scores[101];
long long costs[101];

map<long long, pair<long long, int> > cache;
bool r[1001][101];

pair<long long, int> calc(long long x, long long i)
{
    if (x < 0 || i < 0)
    {
        return make_pair(0, 0);
    }

    if (cache.find(x * 10000 + i) != cache.end())
    {
        return cache[x * 10000 + i];
    }

    pair<long long, int> res = calc(x, i - 1);
    bool choose = false;
    if (x >= costs[i])
    {
        pair<long long, int> t = calc(x - costs[i], i - 1);
        t.first += scores[i];
        t.second += i + 1;
        if (t.first > res.first || t.first == res.first && t.second < res.second)
        {
            res = t;
            choose = true;
        }
    }
    cache[x * 10000 + i] = res;
    r[x][i] = choose;
    return res;
}

void process()
{
    cin >> B;
    cin >> N;

    for (long long i = 0; i < N; ++i)
    {
        cin >> scores[i] >> costs[i];
    }

    cache.clear();
    memset(r, 0, sizeof(r));
    pair<long long, int> totalScore = calc(B, N - 1);

    vector<int> seqs;
    for (int i = N - 1; i >= 0; --i)
    {
        if (r[B][i])
        {
            seqs.push_back(i);
            B -= costs[i];
        }
    }
    sort(seqs.begin(), seqs.end());
    long long totalCost = 0;
    for (int i = 0; i < seqs.size(); ++i)
    {
        totalCost += costs[seqs[i]];
    }
    cout << totalScore.first << ' ' << totalCost << endl;
    if (seqs.size())
    {
        cout << seqs[0] + 1;
    }

    for (int i = 1; i < seqs.size(); ++i)
    {
        cout << ' ' << seqs[i] + 1;
    }
    if (seqs.size())
    {
        cout << endl;
    }
}

int main(void)
{
    long long T;
    cin >> T;
    for (long long i = 1; i <= T; ++i)
    {
        cout << "Case #" << i << ":" << endl;
        process();
    }
    return 0;
}