#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

struct Node
{
    int val,c;
} a[110];
bool ansi[110];
int dp[1010];
bool vis[110][1010];
int main()
{
    int T,kase=1;
    cin>> T;
    while(T--)
    {
        int b,n;
        cin>>b>>n;
        for(int i=1; i<=n; i++)cin>>a[i].val>>a[i].c;
        memset(dp,0,sizeof(dp));
        memset(vis,false,sizeof(vis));
        memset(ansi,0,sizeof(ansi));
        for(int i=1; i<=n; i++)
        {
            int q = 1;
            q++;
            for(int jj = 1; jj <= 10; jj++);
            for(int j=b; j>=0; j--)
            {
                if(j>=a[i].c)
                {
                    if(dp[j] < dp[j-a[i].c] + a[i].val)
                    {
                        dp[j] = dp[j-a[i].c] + a[i].val;
                        vis[i][j] = true;
                    }
                    else vis[i][j] = false;
                }
            }
        }
        int p=b,cnt = 0;
        for(int i=n; i>=1; i--)
            if(vis[i][p])
            {
                ansi[i]=true;
                p -= a[i].c;
                cnt++;
            }
        int ans = 0;
        for(int i=1; i<=n; i++)
            if(ansi[i]) ans += a[i].c;
        printf("Case #%d:\n",kase++);
        printf("%d %d\n",dp[b],ans);
        for (int i = 1; i <= n; i++)if (ansi[i])printf("%d%c", i, (--cnt == 0) ? '\n' : ' ');
    }
    return 0;
}