#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int val[110] , cost[110];
int dpv[1010][110] , dps[1010][110] , pre[1010][110];
int mk[110];
int main()
{
    int T , B , N;
    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" , &val[i] , &cost[i] );
        for( int i=0 ; i<=B ; i++ )
        {
            for( int j=0 ; j<=N ; j++ )
            {
                dpv[i][j] = -1;
                dps[i][j] = -1;
                pre[i][j] = -1;
            }
        }
        dpv[0][0] = 0;
        dps[0][0] = 0;
        for( int i=1 ; i<=N ; i++ )
        {
            if( dpv[0][i-1] < 0 )
            {
                dpv[0][i-1] = 0;
                dps[0][i-1] = 0;
            }
            for( int j=0 ; j<=B ; j++ )
            {
                if( dpv[j][i-1] >= 0 )
                {
                    //cout << "+" << i-1 << "-" << j << endl;
                    int id = N + 1 - i;
                    //cout << id << endl;
                    int nxt = j + cost[id];
                    //cout << nxt << endl;
                    if( nxt <= B && ( dpv[nxt][i] < dpv[j][i-1] + val[id] || ( dpv[nxt][i] == dpv[j][i-1] + val[id] && dps[nxt][i] >= dps[j][i-1] + id ) ) )
                    {
                        dpv[nxt][i] = dpv[j][i-1] + val[id];
                        dps[nxt][i] = dps[j][i-1] + id;
                        pre[nxt][i] = j * 101 + i-1;
                    }
                }
                if( dpv[j][i] < dpv[j][i-1] || ( dpv[j][i] == dpv[j][i-1] && dps[j][i] >= dps[j][i-1] ) )
                {
                    dpv[j][i] = dpv[j][i-1];
                    dps[j][i] = dps[j][i-1];
                    pre[j][i] = pre[j][i-1];
                }
            }
        }
        /*
        for( int i=1 ; i<=N ; i++ )
        {
            for( int j=0 ; j<=B ; j++ )
                cout << dpv[j][i] << " ";
            cout << endl;
        }*/
        int mval = 0 , mins = 101*50+1 , ct = 0 , fid = 101;
        for( int i=0 ; i<=B ; i++ )
        {
            if( dpv[i][N] > mval || dpv[i][N] == mval && dps[i][N] < mins || dpv[i][N] == mval && dps[i][N] == mins && fid > dps[i][N] - dps[ pre[i][N] / 101 ][ pre[i][N] % 101 ] )
            {
                mval = dpv[i][N];
                mins = dps[i][N];
                fid = dps[i][N] - dps[ pre[i][N] / 101 ][ pre[i][N] % 101 ];
                ct = i;
            }
        }

        int p = 0;

        printf( "Case #%d:\n%d %d\n" , cas , mval , ct );
        bool ck = false;
        for( int i=ct*101+N ;  ; i=pre[i/101][i%101] )
        {
            if( dps[i/101][i%101] == 0 ) break;
            if( ck ) printf( " " );
            int pp = pre[i/101][i%101];
            printf( "%d" , dps[i/101][i%101] - dps[pp/101][pp%101] );
            ck = true;
        }
        if(ck) printf( "\n" );
    }
    return 0;
}

/*
55
20 5
2 3
5 1
2 4
0 3
3 0
*/