#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<limits.h>  
#include<math.h>  
#include<algorithm>  
using namespace std;  
using namespace std;  
int dp[2005],score[1005],cost[1005],vis[1005][1005];  
int main (void)
{
    int T;  
    scanf ("%d",&T);  
    int cases=1;  
    while (T--)
    {  
        int b,n;  
        scanf ("%d%d",&b,&n);  
        for (int i=1;i<=n;i++)
            scanf("%d%d",&score[i],&cost[i]);   
        memset(dp,0,sizeof(dp));  
        memset(vis,0,sizeof(vis));  
        long long maxdp=0;  
        for (int i=1;i<=n;i++)
        {  
            for (int j=b;j>=cost[i];j--)
            {  
                if (dp[j]<dp[j-cost[i]]+score[i])
                {  
                    dp[j]=dp[j-cost[i]]+score[i];  
                    vis[i][j]=1;  
                }  
            }  
        }  
        int i=n,j=b;  
        int ans=0;  
        int count0[1005];  
        int len=0;  
       // memset(count0,0,sizeof(count0));  
        while (i>0)
        {  
            if(vis[i][j])
            {  
                j-=cost[i];  
                ans+=cost[i];  
                count0[len]=i;  
                len++;  
            }  
            i--;  
        }  
        sort(count0,count0+len);  
        printf ("Case #%d:\n",cases++);  
        printf ("%d %d\n",dp[b],ans);  
        for (int i=0;i<len;i++)
        {  
            if (i)  
                printf (" ");  
            printf ("%d",count0[i]);  
            if(i==len-1)  
                printf ("\n");  
        }  
    }      
    return 0;  
}