#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100 + 5
#define M 1000 + 5
#define INF 593119681
#define mp make_pair

int Case, Test, b, n, ans, Dp[N][M][4], Fa[N][M][2], A[N];

int main()
{
    for (scanf("%d", &Case); Case --; )
    {
        scanf("%d%d", &b, &n);
        for (int i = 0; i <= n; i ++)
            for (int j = 0; j <= b; j ++)
            {
                for (int k = 0; k < 2; k ++)
                    Fa[i][j][k] = 0;
                Dp[i][j][0] = Dp[i][j][3] = -INF;
                Dp[i][j][2] = 0;
                Dp[i][j][1] = INF;
            }
        Dp[0][0][0] = Dp[0][0][1] = Dp[0][0][2] = Dp[0][0][3] = 0;
        for (int i = 1, w, v; i <= n; i ++)
        {
            scanf("%d%d", &w, &v);
            for (int j = 0; j <= b; j ++)
            {
                Dp[i][j][0] = Dp[i - 1][j][0], Dp[i][j][1] = Dp[i - 1][j][1];
                Dp[i][j][2] = Dp[i - 1][j][2], Dp[i][j][3] = Dp[i - 1][j][3];
                Fa[i][j][0] = j, Fa[i][j][1] = 0;
            }
            for (int j = v; j <= b; j ++)
                if (mp(mp(Dp[i - 1][j - v][0] + w, -(Dp[i - 1][j - v][1] + i)), mp(Dp[i - 1][j - v][2] + 1, Dp[i - 1][j - v][3])) >= mp(mp(Dp[i][j][0], -Dp[i][j][1]), mp(Dp[i][j][2], Dp[i - 1][Fa[i][j][0]][3])))
                {
                    Dp[i][j][0] = Dp[i - 1][j - v][0] + w, Dp[i][j][1] = Dp[i - 1][j - v][1] + i;
                    Dp[i][j][2] = Dp[i - 1][j - v][2] + 1, Dp[i][j][3] = i;
                    Fa[i][j][0] = j - v, Fa[i][j][1] = 1;
                }
        }
        int Max = 0;
        for (int j = 1; j <= b; j ++)
            if (mp(mp(Dp[n][j][0], -Dp[n][j][1]), mp(Dp[n][j][2], Dp[n][j][3])) > mp(mp(Dp[n][Max][0], -Dp[n][Max][1]), mp(Dp[n][Max][2], Dp[n][Max][3])))
                Max = j;
        ans = Dp[n][Max][0], A[0] = 0;
        for (int i = n, j = Max; i; j = Fa[i --][j][0])
            if (Fa[i][j][1]) A[++ A[0]] = i;
        reverse(A + 1, A + A[0] + 1);
        printf("Case #%d:\n", ++ Test);
        printf("%d %d\n", ans, Max);
        for (int i = 1; i <= A[0]; i ++)
            printf("%d%c", A[i], i == A[0] ? '\n' : ' ');
    }
    return 0;
}