#include<bits/stdc++.h>
using namespace std;
const int inf=(1<<30)-1;
const int maxn=100010;
#define REP(i,n) for(int i=(0);i<(n);i++)
#define FOR(i,j,n) for(int i=(j);i<=(n);i++)
typedef long long ll;
struct data{
    int v,w;
    int id;
}a[maxn];
int dp[maxn];
bool pre[110][1010];
int ans[maxn];
int n,m;
void init()
{
    memset(pre,0,sizeof(pre));
    memset(dp,0,sizeof(dp));
    memset(ans,0,sizeof(ans));
}
int main()
{
    int T;scanf("%d",&T);
    int Cas=0;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&a[i].v,&a[i].w);
            a[i].id=i;
        }
        for(int i=1;i<=m;i++)
        for(int j=n;j>=a[i].w;j--)
        if(dp[j-a[i].w]+a[i].v>dp[j])
        {
            dp[j]=dp[j-a[i].w]+a[i].v;
            pre[i][j]=1;
        }
        int sum1=0,sum2=0;
        int k=0;
        int j=n;
        for(int i=m;i>=1;i--)
        if(pre[i][j]) {
            sum1+=a[i].v;
            sum2+=a[i].w;
            ans[++k]=a[i].id;
            j-=a[i].w;
        }
        printf("Case #%d:\n",++Cas);
        printf("%d %d\n",sum1,sum2);
        sort(ans+1,ans+k+1);
        for(int i=1;i<=k;i++)
        {
            if(i>1) printf(" ");
            printf("%d",ans[i]);
            if(i==k) puts("");
        }
    }
    return 0;
}