#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>

#define lc(x) ns[x].l
#define rc(x) ns[x].r

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

struct io_s {

    bool negative;
    char ch;

    inline bool isdigitx(char c) {
        return c >= '0' && c <= '9';
    }

    template<typename T>
    bool rn(T& _v) {
        negative = false;
        _v = 0;
        while (!isdigitx(ch = getchar()) && ch != EOF) { negative = ch == '-'; };
        if (ch == EOF)return false;
        do { _v = _v * 10 + ch - '0'; } while (isdigitx(ch = getchar()));
        if (negative) _v = -_v;
        return true;
    }

    template<typename T>
    bool run(T& _v) {
        _v = 0;
        while (!isdigitx(ch = getchar()) && ch != EOF) {};
        if (ch == EOF)return false;
        do { _v = _v * 10 + ch - '0'; } while (isdigitx(ch = getchar()));
        return true;
    }

    template<typename T>
    inline T r() {
        T v = T();
        rn(v);
        return v;
    }

    inline int ri() { return r<int>(); }
    inline ll rll() { return r<ll>(); }

    template<class T>
    inline void o(T p) {
        static int stk[70], tp;
        if (p == 0) { putchar('0'); return; }
        if (p < 0) { p = -p; putchar('-'); }
        while (p) stk[++tp] = p % 10, p /= 10;
        while (tp) putchar(stk[tp--] + '0');
    }
    inline void ln() { putchar('\n'); }

    inline void space() { putchar(' '); }

    template<class T>
    inline void oln(T p) {
        o(p); ln();
    }

} io;

void Case(int t) {
    printf("Case #%d:\n", t);
}

const int N = 100 + 5;
const int M = 1e3 + 10;

int m, n;

int a[N], b[N];

int c[M], ids[M], idc[M];

vector<int> id[M];

int main()
{
    int T = io.ri();
    for (int TT = 1; TT <= T; ++TT) {
        Case(TT);
        io.rn(m); io.rn(n); bool flag = true;
        for (int i = 1; i <= n; ++i) {
            io.rn(a[i]); io.rn(b[i]);
            if (b[i] <= m)flag = false;
        }
        if (flag) {
            puts("0 0");
            continue;
        }
        memset(c, -1, sizeof c);
        c[0] = 0;
        id[0].clear();
        idc[0] = ids[0] = 0;
        for (int i = 1; i <= n; ++i) {
            if (a[i] == 0 && b[i] == 0) continue;
            for (int j = m - b[i]; j >= 0; --j) if (c[j] >= 0) {
                if (b[i] == 0) {
                    c[j] += a[i];
                    id[j].push_back(i);
                    ids[j] += i;
                    ++idc[j];
                    continue;
                }
                int x = j + b[i];
                if (x > m) continue;
                if (c[j] + a[i] > c[x]) {
                    c[x] = c[j] + a[i];
                    id[x] = id[j];
                    id[x].push_back(i);
                    ids[x] = ids[j] + i;
                    idc[x] = idc[j] + 1;
                }
                else if (c[j] + a[i] == c[x]) {
                    if (ids[j] + i >= ids[x])continue;
                    id[x] = id[j];
                    id[x].push_back(i);
                    ids[x] = ids[j] + i;
                    idc[x] = idc[j] + 1;
                }
            }
        }
        int mc = c[m], mcd = ids[m], mi = m;
        for (int i = m - 1; i > 0; --i) {
            if (c[i] > mc) {
                mc = c[i];
                mi = i;
                mcd = ids[i];
            }
            if (c[i] == mc && ids[i] < mcd) {
                mi = i;
                mcd = ids[i];
            }
        }
        io.o(mc); io.space(); io.oln(mi);
        io.o(id[mi][0]);
        for (int i = 1; i < id[mi].size(); ++i) {
            io.space(); io.o(id[mi][i]);
        }
        io.ln();
    }
    return 0;
}