#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 100 + 100;
const int MAXM = 1000 + 100;

struct State
{
    int val, sum;
    vector<int> arr;
    State(int _v = 0, int _s = 0, const vector<int> &_a = vector<int>()) : 
    val(_v), sum(_s), arr(_a)
    {}
    bool operator < (const State &s) const
    {
        if(val != s.val) return val < s.val;
        if(sum != s.sum) return sum > s.sum;
        return arr > s.arr;
    }
    State operator + (const State &s) const
    {
        State ret(val + s.val, sum + s.sum, arr);
        ret.arr.insert(ret.arr.end(), s.arr.begin(), s.arr.end());
        return ret;
    }
};

int n, m;
int cost[MAXM], val[MAXN];
State f[MAXN][MAXM];
bool vis[MAXN][MAXM];
vector<int> ans;

void init()
{
    for(int i = 0; i <= n + 1; i++)
        for(int j = 0; j <= m + 1; j++)
            f[i][j] = State(), vis[i][j] = false;
    ans.clear();
}

void solve()
{
    for(int j = 0; j <= m; j++)
        f[0][j] = State(0, 0), vis[0][j] = true;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= m; j++)
        {
            if(vis[i - 1][j])
            {
                vis[i][j] = true;
                f[i][j] = f[i - 1][j];
            }
            if(j - cost[i] >= 0 && vis[i - 1][j - cost[i]])
                if(!vis[i][j] || f[i][j] < f[i - 1][j - cost[i]] + State(val[i], i, vector<int>(1, i)))
                {
                    vis[i][j] = true;
                    f[i][j] = f[i - 1][j - cost[i]] + State(val[i], i, vector<int>(1, i));
                }
        }
    ans = f[n][m].arr;
}

void work()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i++)
        cin >> val[i] >> cost[i];
    init();
    solve();
    int sumv = 0, sumc = 0;
    for(int i = 0; i < ans.size(); i++)
        sumv += val[ans[i]], sumc += cost[ans[i]];
    cout << sumv << ' ' << sumc << endl;
    if(ans.size())
    {
        for(int i = 0; i < ans.size(); i++)
            cout << ans[i] << (i + 1 < ans.size() ? " " : "");
        cout << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
//    freopen("1.in", "r", stdin);
//    freopen("1.out", "w", stdout);

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