#include<iostream>
#include<algorithm>
#include<iomanip>
#include<string>
#include<map>
#include<sstream>
#include<vector>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<list>
using namespace std;
struct A
{
    int value;
    int cost; 
    bool choose[111];
    int sumchoose;
}dp[1111];
int score[111],cost[111];
int n,t;
void into()
{
    int i,j;
    for(i=0;i<=t;i++)
    {
        dp[i].value=0;
        dp[i].cost=0;
        dp[i].sumchoose=0;
        for(j=1;j<=n;j++)
        {
            dp[i].choose[j]=0;
        }
    }
}
void changechoose(int x,int y,int k)
{
    for(int i=1;i<=n;i++)
    {
        dp[x].choose[i]=dp[y].choose[i];
    }
    dp[x].choose[k]=1;
}
int main()
{
    int j,i,rs=0,r;
    scanf("%d",&r);
    while(r--)
    {
        scanf("%d",&t);
        scanf("%d",&n);
        score[0]=cost[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d %d",&score[i],&cost[i]);
        }
        into();
        for(i=1;i<=n;i++)
        {
            for(j=t;j>=cost[i];j--)
            {
                if(dp[j].value<dp[j-cost[i]].value+score[i]||(dp[j].value==dp[j-cost[i]].value+score[i]&&dp[j].sumchoose>dp[j-cost[i]].sumchoose+i))
                {
                    changechoose(j,j-cost[i],i);
                    dp[j].value=dp[j-cost[i]].value+score[i];
                    dp[j].cost=dp[j-cost[i]].cost+cost[i];
                    dp[j].sumchoose=dp[j-cost[i]].sumchoose+i;
                }
            }
        }
        rs++;
        printf("Case #%d:\n",rs);
        printf("%d %d\n",dp[t].value,dp[t].cost);
        int f=0;
        for(i=1;i<=n;i++)
        {
            if(dp[t].choose[i])
            {
                if(f)printf(" ");
                printf("%d",i);
                f=1;
            }
        }
        if(f)puts("");
    }
}