#include <bits/stdc++.h>
#define ll long long 
using namespace std;
typedef pair<int,ll> pll;
const int INF = 0x3f3f3f3f;
const int maxn=100+5;

int n,m,val[1005],w[1005];
int d[1005],path[1005][1005];
vector<int> ans;

long double aw(long double x1,long double y1,long double x2,long double y2) {
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

long double cv(long double a,long double b,long double c) {
    return acos((b*b+c*c-a*a)/(2*b*c));
}

int oneNumInBinary(ll n) { 
    ll cnt=0;
    while(n)  n=n&(n-1),cnt++;
    return cnt;
}

ll qpow(ll a,ll b) {
    ll ans=1;    
    while(b) {       
        if(b&1) ans=(ans*a)%999;        
        a=a*a%999;      
        b>>=1;    
    }   
    return ans;
}

inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

inline string readstring() {
    string str;
    char s=getchar();
    while(s==' '||s=='\n'||s=='\r') {s=getchar();}
    while(s!=' '&&s!='\n'&&s!='\r') {str+=s; s=getchar();}
    return str;
}

int main()
{
    int kase=0;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);  scanf("%d",&m);
        for(int i=1;i<=m;i++)  scanf("%d%d",&val[i],&w[i]);
        memset(d,0,sizeof(d));
        memset(path,0,sizeof(path));

        for(int i=1; i<=m; i++) {
            for(int j=n; j>=w[i]; j--) {
                if(d[j-w[i]]+val[i]>d[j]) {
                    d[j]=d[j-w[i]]+val[i];
                    path[i][j]=1;
                }
            }
        }
        printf("Case #%d:\n",++kase);
        int sum=0;
        ans.clear();
        for(int i=m,j=n; i>=1&&j>=0; i--) {
            if(path[i][j]) {
                ans.push_back(i);
                j-=w[i];
                sum+=w[i];
            }
        }
        printf("%d %d\n",d[n],sum);
        sort(ans.begin(),ans.end());
        int sz=ans.size();
        for(int i=0; i<sz; i++)
            printf("%d%c",ans[i],i==sz-1?'\n':' ');
    }
    return 0;
}