#include <iostream>
#include <string>
#include <cstring>
#include<cstdio>
#define INF 0x3f3f3f3f
#define MAXN 100005

using namespace std;
int n,V;
struct Node{
    int v;
    string path;
    void Init()
    {
        string init(n,'0');
        v = 0;
        path = init;
    }
}dp[MAXN];
int val[MAXN];
int vol[MAXN];
int c[MAXN];
int main()
{
    int t = 1;
    int cases;
    scanf("%d",&cases);
    while(cases--)
    {
        scanf("%d%d",&V,&n);
        for(int i=1;i<=n;i++)
            cin>>val[i]>>vol[i];
        for(int i=0;i<=V;i++)
        {
            dp[i].Init();
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=V;j>=vol[i];j--)
            {
                if(dp[j].v<dp[j-vol[i]].v+val[i])
                {
                    dp[j].v=dp[j-vol[i]].v+val[i];
                    dp[j].path=dp[j-vol[i]].path;
                    dp[j].path[i-1]='1';
                }
            }
        }
        int ans  = 0;
        printf("Case #%d:\n",t++);
        if(dp[V].v!=0){
        string ss = dp[V].path;
        int cnt = 0;
        for(int i=0;i<ss.length();i++)
            if(ss[i]=='1') {c[cnt++] = i+1;ans+=vol[i+1];}
            cout<<dp[V].v<<" "<<ans<<endl;
        for(int i=0;i<cnt;i++)
        {
            if(i!=0) printf(" ");
            printf("%d",c[i]);
        }
        }
        else printf("0 0");
        printf("\n");
    }
    return 0;
}