#include <bits/stdc++.h>
using namespace std;
int value[105];
int cost[105];
int dp[1005];
vector<int> vec[1005];
int sum[1005];
int main()
{
    int T;
    cin >> T;
    for (int cas = 1; cas <= T; cas++)
    {
        memset(dp, 0, sizeof(dp));
        int n, m;
        cin>>n>>m;
        for (int i = 1; i <= n; i++)
        {
            vec[i].clear();
            sum[i] = 0;
        }
        for (int i = 1; i <= m; i++)
        {
            cin>>value[i]>>cost[i];
        }
        for (int i = 1; i <= m; i++)
        {
            for (int j = n; j >= 0; j--)
            {
                if (j >= cost[i])
                {
                    if (dp[j] < dp[j - cost[i]] + value[i])
                    {
                        vec[j] = vec[j - cost[i]];
                        vec[j].push_back(i);
                        sum[j] = sum[j - cost[i]];
                        sum[j] += i;
                        dp[j] = dp[j - cost[i]] + value[i];
                    }
                    else if (dp[j] == dp[j - cost[i]] + value[i])
                    {
                        if (sum[j] > sum[j - cost[i]] + i)
                        {
                            sum[j] = sum[j - cost[i]];
                            sum[j] += i;
                        }
                    }
                }
            }
        }
        cout<<"Case #"<<cas<<":"<<endl;
        int ans = 0;
        for (int i = 0; i < vec[n].size(); i++)
        {
            ans += cost[vec[n][i]];
        }
        cout<<dp[n]<<" "<<ans<<endl;
        int flag = 0;
        for (int i = 0; i < vec[n].size(); i++)
        {
            flag = 1;
            printf(i == 0 ? "%d" : " %d", vec[n][i]);
        }
        if (flag)
        {
            printf("\n");
        }
    }
    return 0;
}