#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=110,M=1010;
struct PII{
        int score,cost;
}a[N];
int f[M];
int n,m;
int money;
bool st[N][M];
bool ans[N]={false}; 
int main()
{
    cin>>m;
    for(int t=1;t<=m;t++)
    {
        memset(st,0,sizeof st);
        memset(f,0,sizeof f);
        memset(ans,false,sizeof ans);
        cin>>money>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].score>>a[i].cost;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=money;j>=a[i].cost;j--)
            {
                if(f[j]<f[j-a[i].cost]+a[i].score)
                {
                    f[j]= f[j-a[i].cost]+a[i].score;
                    st[i][j]=true;
                 } 
            }
        }
        int x=money;
        int cnt=0;
        for(int i=n;i>0;i--)
        {
            if(st[i][x])
            {
                ans[i]=true;
                x-=a[i].cost;
                cnt++;
            }
        }
        printf("Case #%d:\n", t);
        printf("%d %d\n",f[money],money-x);
        for(int i=1;i<=n;i++)
        {
            if(ans[i])
            {
                printf("%d%c",i,(--cnt==0)?'\n':' ');
            }
        }
     }
     return 0;
}