//wtrl,everybody hangbeat me
#include<bits/stdc++.h>
/*#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>*/
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef pair<ll,ll> pll;
/*=====================================================================*/
#define pb push_back
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(s) (s).begin(),(s).end()
#define repd(i,n) for(int i=n-1;i>=0;i--)
#define forn(i,p,n) for(int i=p;i<=n;i++)
#define ford(i,p,n) for(int i=n;i>=p;i--)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();++i)
#define INF 1e9
#define PI acos(-1)
/*=====================================================================*/
string int_to_string(ll n)
{
    string s="";
    while(n)
    {
        ll now=n%10;
        s+=now+'0';
        n/=10;
    }
    reverse(s.begin(),s.end());
    return s;
}
ll string_to_int(string s)
{
    ll n=0;
    rep(i,s.size())
    {
        n*=10;
        n+=s[i]-'0';
    }
    return n;
}
/*======================================================================*/
const int dx[]={-1,0,1,0};
const int dy[]={0,-1,0,1};
const int month[2][12]={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};
//think twice,code once
//think once,debug forever
int score[110];
int cost[110];
ll dp[1010];
bool use[1010][110]; 
void solve(int CASE)
{
    int b,n;
    cin>>b>>n;
    forn(i,1,n)
    {
        cin>>score[i]>>cost[i];
    }
    forn(i,0,b)
    {
        dp[i]=0;
    }
    memset(use,0,sizeof(use));
    dp[0]=0;
    forn(i,1,n)
    {
        ford(j,0,b)
        {
            if(j-cost[i]<0)
            {
                continue;
            }
            if(dp[j]<dp[j-cost[i]]+score[i])
            {
                dp[j]=dp[j-cost[i]]+score[i];
                //path[j]=path[j-cost[i]]+i;
                use[j][i]=1;
                //last[j]=i;
            }
            /*else
            {
                if(dp[j]==dp[j-cost[i]]+score[i])
                {
                    if(path[j]>path[j-cost[i]]+i)
                    {
                        path[j]=path[j-cost[i]]+i;
                        use[j][i]=1;
                        last[j]=i;    
                    }
                }
            }*/
        }
        /*forn(j,0,b)
        {
            if(dp[j]==-1e18)
            {
                cout<<'x'<<" ";    
            } 
            else
            {
                cout<<dp[j]<<" ";
            }
        }
        cout<<endl;*/
    }
    /*forn(i,0,b)
    {
        cout<<dp[i]<<endl;
    }*/
    /*ll maxdp=0,minpath=1e18,id=0;
    forn(i,1,b)
    {
        if(dp[i]>=1e18)
        {
            continue;
        }
        if(dp[i]>maxdp)
        {
            maxdp=dp[i];
            minpath=path[i];
            id=i;
        }
        else
        {
            if(dp[i]==maxdp)
            {
                if(path[i]<minpath)
                {
                    minpath=path[i];
                    id=i;
                }
            }
        }
    }*/
    vi ans;
    int now=b,sum=0;
    ford(i,1,n)
    {
        if(use[now][i])
        {
            ans.pb(i);
            now-=cost[i];
            sum+=cost[i];
        }
    }
    cout<<"Case #"<<CASE<<":"<<endl;
    cout<<dp[b]<<" "<<sum<<endl;
    /*while(now)
    {
        cout<<now<<" "<<last[now]<<" "<<cost[last[now]]<<endl;
        ans.pb(last[now]);
        now-=cost[last[now]];
    }*/
    if(ans.size()==0)
    {
        return;
    }
    sort(all(ans));
    rep(i,ans.size()-1)
    {
        cout<<ans[i]<<" ";
    }
    cout<<ans[ans.size()-1];
    cout<<endl;
}
/*======================================================================*/
signed main()
{
    std::ios::sync_with_stdio(false);
  /*
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
  */
  /*====================================================================*/
  int t=1,CASE=0;
  cin>>t;
  while(t--)
  {
      CASE++;
      solve(CASE);
  }
  return 0;
}
/*
注意数组越界，vector长度为0的时候循环会RE
注意输入顺序
注意循环时int*int爆ll
注意答案存爆ll
存答案用string过慢，最好直接输出或者用vector<char>
memset是O(n)
*/