//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
//作者:中国江苏南京丁天行
using namespace std;
//数组不要开小了
//数组不要开反了
int t,b,n,_,s[105],c[105];
int f[105][1005],g[105][1005];
void cty(){
     scanf("%d%d",&b,&n);
     for(int i=1;i<=n;i++)scanf("%d%d",s+i,c+i);  
     printf("Case #%d:\n",_);
     if(n==0){
              printf("0 0\n");
              return;
     }
     memset(f,0,sizeof(f));
     memset(g,0,sizeof(g));
     for(int i=1;i<=n;i++){
             for(int j=0;j<=b;j++)f[i][j]=f[i-1][j];
             for(int j=c[i];j<=b;j++){
                     if(f[i][j]<f[i-1][j-c[i]]+s[i]){
                                                     f[i][j]=f[i-1][j-c[i]]+s[i];
                                                     g[i][j]=1;
                     }
             }
     }
     vector<int> v;
     int x=b;
     for(int i=n;i;i--)if(g[i][x])v.pb(i),x-=c[i];
     printf("%d %d\n",f[n][b],b-x);
     if(v.size()){
                  for(int i=v.size()-1;i>0;i--)printf("%d ",v[i]);
                  printf("%d\n",v[0]);
     }
}    
int main()
{
    scanf("%d",&t);
    while((++_)<=t)cty();
    //system("pause");
    return 0;
}