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

using namespace std;

typedef pair<vector<int>, int> pvi;

const int maxn = 1000 + 5;

int dp[maxn][maxn], sum[maxn][maxn], score[maxn], cost[maxn];
pvi p[maxn];

int main()
{
    int T, cas = 0;
    scanf("%d", &T);
    while(T--)
    {
        int m, n;
        scanf("%d%d", &m, &n);
        memset(dp, 0x8f, sizeof(dp));
        memset(sum, 0, sizeof(sum));
        dp[n + 1][0] = 0;
        for(int i = 1; i <= n; ++i) scanf("%d%d", &score[i], &cost[i]);
        for(int i = n; i > 0; --i)
        {
            for(int j = m; j >= 0; --j)
            {
                dp[i][j] = dp[i + 1][j];
                sum[i][j] = sum[i + 1][j];
                int k = j - cost[i];
                if(j < cost[i] || score[i] == 0 || dp[i + 1][k] < 0) continue;
                if(dp[i][j] < dp[i + 1][k] + score[i])
                {
                    dp[i][j] = dp[i + 1][k] + score[i];
                    sum[i][j] = sum[i + 1][k] + i;
                }
                else if(dp[i][j] == dp[i + 1][k] + score[i] && sum[i][j] > sum[i + 1][k] + i)
                {
                    sum[i][j] = sum[i + 1][k] + i;
                }
            }
        }
        printf("Case #%d:\n", ++cas);
        int ans = dp[1][0], tot = sum[1][0];
        for(int i = 1; i <= m; ++i)
        {
            if(ans < dp[1][i])
            {
                ans = dp[1][i];
                tot = sum[1][i];
            }
            else if(ans == dp[1][i] && tot > sum[1][i])
            {
                tot = sum[1][i];
            }
        }
        int cnt = 0;
        for(int i = 0; i <= m; ++i)
        {
            if(ans == dp[1][i] && tot == sum[1][i])
            {
                p[cnt].first.clear();
                for(int k = 1, j = i; k <= n; ++k)
                {
                    if(score[k] != 0 && j >= cost[k] && dp[k][j] == dp[k + 1][j - cost[k]] + score[k] && sum[k][j] == sum[k + 1][j - cost[k]] + k)
                    {
                        p[cnt].first.push_back(k);
                        j -= cost[k];
                    }
                }
                p[cnt++].second = i;
            }
        }
        sort(p, p + cnt);
        printf("%d %d\n", ans, p[0].second);
        for(int i = 0; i < p[0].first.size(); ++i)
        {
            printf("%d%c", p[0].first[i], " \n"[i == p[0].first.size() - 1]);
        }
    }
    return 0;
}