#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int B = 1005;

int b, n, answ;
int s[N], c[N];
pair<int, int> f[B], ans;
bitset<N> bs[B], ansbs;

template <typename T, typename U>
pair<T, U> operator + (const pair<T, U> &lhs, const pair<T, U> &rhs)
{
    return make_pair(lhs.first + rhs.first, lhs.second + rhs.second);
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas)
    {
        scanf("%d%d", &b, &n);
        for (int i = 1; i <= n; ++i)
            scanf("%d%d", s+i, c+i);
        for (int i = 1; i <= b; ++i) f[i] = make_pair(-1, -1);
        ans = f[0] = make_pair(0, 0);
        for (int i = 0; i <= b; ++i) bs[i].reset();
        ansbs.reset();
        answ = 0;
        for (int i = n; i >= 1; --i)
            for (int j = b; j >= c[i]; --j) if (f[j-c[i]].first != -1)
            {
                if (f[j] <= f[j-c[i]] + make_pair(s[i], -i))
                {
                    f[j] = f[j-c[i]] + make_pair(s[i], -i);
                    bs[j] = bs[j-c[i]];
                    bs[j].set(i);
                    if (f[j] >= ans)
                    {
                        ans = f[j];
                        ansbs = bs[j];
                        answ = j;
                    }
                }
            }
        printf("Case #%d:\n", cas);
        printf("%d %d\n", ans.first, answ);
        vector<int> out;
        for (int i = 1; i <= n; ++i)
            if (ansbs[i]) out.push_back(i);
        for (size_t i = 0; i < out.size(); ++i)
            printf("%d%c", out[i], " \n"[i + 1 == out.size()]);
    }
    return 0;
}