#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 1005
#define ll long long

using namespace std;

int n,m;
ll dp[1005];
ll cost[105],val[105];
vector<int> G[1005];

int main()
{
    int tt;
    scanf("%d",&tt);
    for(int t=1; t<=tt; t++)
    {
        scanf("%d%d",&m,&n);
        for(int i=1; i<=n; i++)
            scanf("%lld%lld",&val[i],&cost[i]);
        memset(dp,0,sizeof dp);
        dp[0] = 0;
        for(int i=1; i<=n; i++)
        {
            for(int j=m; j>=cost[i]; j--)
            {
                if(dp[j] < dp[j-cost[i]]+val[i])
                {
                    dp[j] = dp[j-cost[i]]+val[i];
                    G[j] = G[j-cost[i]];
                    G[j].push_back(i);
                }
            }
        }
        ll ccc = 0;
        for(int i=0; i<G[m].size(); i++)
            ccc += cost[G[m][i]];
        printf("Case #%d:\n",t);
        printf("%lld %lld\n",dp[m],ccc);
        for(int i=0; i<G[m].size(); i++)
        {
            printf("%d",G[m][i]);
            if(i!=G[m].size()-1)
                printf(" ");
            else
                printf("\n");
        }
        for(int i=0; i<=m; i++)
            G[i].clear();
    }


    return 0;
}