#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int maxb = 1e3 + 5 , maxn = 100 + 5;

bool flag;
int t , b , n;
int num[maxn];
int f[maxn][maxb] , from[maxn][maxb] , cho[maxn][maxb] , used[maxn][maxb];

void get_num(int now , int pos)
{
    if (now < 1)
        return;
    get_num(now - 1 , from[now][pos]);
    if (cho[now][pos])
        num[++num[0]] = now;
}

int main()
{
    //freopen("1004.out" , "w" , stdout);
    scanf("%d" , &t);
    for (int kase = 1; kase <= t; kase++)
    {
        scanf("%d" , &b);
        scanf("%d" , &n);
        for (int i = 1; i <= n; i++)
        {
            int v , w;
            scanf("%d %d" , &v , &w);
            for (int j = 0; j <= b; j++)
            {
                f[i][j] = f[i - 1][j];
                from[i][j] = j;
                cho[i][j] = 0;
                used[i][j] = used[i - 1][j];
                if (j >= w)
                    if (f[i - 1][j - w] + v > f[i][j])
                    {
                        f[i][j] =  f[i - 1][j - w] + v;
                        from[i][j] = j - w;
                        cho[i][j] = 1;
                        used[i][j] = used[i - 1][j - w] + w;
                    }
            }
        }
        printf("Case #%d:\n" , kase);
        printf("%d %d\n" , f[n][b] , used[n][b]);
        num[0] = 0;
        get_num(n , b);
        if (num[0])
        {
            for (int i = 1; i < num[0]; i++)
                printf("%d " , num[i]);
            printf("%d\n" , num[num[0]]);
        }
    }
    return 0;
}