#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 105
#define maxm 1005
using namespace std;

int n,m;
int score[maxn],cost[maxn];

bool used[maxn][maxm];
int dp[maxn][maxm];
int track[maxn][maxm];

bool chosed[maxn];

bool init()
{
    scanf("%d%d",&m,&n);
    for (int i=1;i<=n;++i)
        scanf("%d%d",&score[i],&cost[i]);
}

int Score,Cost,Sum;

void solve()
{
    memset(chosed,0,sizeof(chosed));
    memset(track,0x3f,sizeof(track));
    memset(used,0,sizeof(used));
    memset(dp,0,sizeof(dp));
    
    track[n+1][0]=0;
     
    Score=0,Cost=0,Sum=n*n;
    for (int i=n;i;--i)
        for (int j=0;j<=m;++j)
        {
            dp[i][j]=dp[i+1][j];
            track[i][j]=track[i+1][j];
            if (j>=cost[i])
            {
                if (dp[i][j]==dp[i+1][j-cost[i]]+score[i])
                {
                    if (track[i][j]>=track[i+1][j-cost[i]]+i)
                    {
                        used[i][j]=1;
                        track[i][j]=track[i+1][j-cost[i]]+i;
                    }
                }
                
                if (dp[i][j]<dp[i+1][j-cost[i]]+score[i])
                {
                    used[i][j]=1;
                    dp[i][j]=dp[i+1][j-cost[i]]+score[i];
                    track[i][j]=track[i+1][j-cost[i]]+i;
                }
                
            }
            if (Score<dp[i][j])
            {
                Score=dp[i][j];
                Sum=track[i][j];
            }
            
            if (Score==dp[i][j])
                Sum=min(Sum,track[i][j]);
            
//            printf("dp[%d][%d]=%d track[%d][%d]=%d used[%d][%d]=%d\n",i,j,dp[i][j],i,j,track[i][j],i,j,used[i][j]);
        }
    
//    cout<<Score<<" "<<Sum<<endl;
    
    int cmp=Score;
    for (int i=1;i<=n;++i)
    {
//        cout<<i<<":"<<Sum<<" "<<cmp<<endl;
        for (int j=0;j<=m;++j)
            if (track[i][j]==Sum&&dp[i][j]==cmp&&used[i][j])
            {
                chosed[i]=1;
                Sum-=i;
                cmp-=score[i];
                Cost+=cost[i];
                break;
            }
    }
    
    printf("%d %d\n",Score,Cost);
    
    bool flag=0;
    for (int i=1;i<=n;++i)
        if (chosed[i])
        {
            if (flag)
                putchar(' ');
            else
                flag=1;
            printf("%d",i);
        }
    
    if (Score==0&&Cost==0)    return;
    putchar('\n');
}

int main()
{
//    freopen("c.in","r",stdin);
    int T,icase=0;
    scanf("%d",&T);
    while (T--)
    {
        printf("Case #%d:\n",++icase);
        init();
        solve();
    }
    return 0;
}