#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
const int maxn = 1009;
int n , m;

struct node
{
    int score , sum;
    string choose;
    void init()
    {
        sum = 0;
        score = -1000000;
        choose = "";
    }
}f[maxn];

bool cmp( node &x , node &y , int score = 0 , int i = 0 ) //看y+一个菜是否能更新x
{
    if ( x.score < y.score + score ) return true;
    if ( x.score == y.score + score )
    {
        if ( x.sum > y.sum + i ) return true;
        if ( x.sum == y.sum + i )
        {
            string temp = y.choose;
            if ( i != 0 ) temp+=(char)(i+'0');
            return x.choose > temp;
        }
    }
    return false;
}

void init()
{
    int score_i , cost_i;
    cin>>n>>m;
    for( int i = 0; i <= n; i++ ) f[i].init();
    f[0].score = 0;
    for( int i = 1; i <= m; i++ )
    {
        scanf("%d%d",&score_i,&cost_i);
        for( int j = n; j >= cost_i; j-- )
        if ( cmp( f[j] , f[j-cost_i] , score_i , i ) )
        {
            f[j].score = f[j-cost_i].score + score_i;
            f[j].sum = f[j-cost_i].sum + i;
            f[j].choose = f[j-cost_i].choose + (char)('0'+i);
        }
    }
}

int main()
{
    int T;
    cin>>T;
    for( int kase = 1; kase <= T; kase++ )
    {
        int k = 0;
        init();
        printf("Case #%d:\n",kase);
        for( int i = 1; i<= n; i++ )
            if ( cmp( f[0] , f[i] ) ) f[0] = f[i] , k = i;
        if ( f[0].choose == "" )
            puts("0 0");
        else{
            printf("%d %d\n" , f[0].score , k );
            for( int i = 0; i < f[0].choose.size(); i++ )
                printf("%d%c",(int)(f[0].choose[i]-48+256)%256,(i==f[0].choose.size()-1)?'\n':' ');
        }
    }
    return 0;
}