#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=1010;
int cas,n,m,i,j,a[M],b[M],A[M],B[M],dp[110][M],sum[110][M],pre[110][M],Ans[M];
int calc(int x,int y,int z,int w){
    A[0]=0;
    for (int i=x;i;i--)
        if (pre[i][y]){
            y-=b[i];
            A[++A[0]]=i;
        }
    B[0]=0;
    for (int i=z;i;i--)
        if (pre[i][w]){
            w-=b[i];
            B[++B[0]]=i;
        }
    for (int i=1;i<=min(A[0],B[0]);i++)
        if (A[i]<B[i])return 1;
            else if (A[i]>B[i])return 0;
    return 0;
}
int main(){
    scanf("%d",&cas);
    for (int dc=1;dc<=cas;dc++){
        scanf("%d%d",&m,&n);
        for (i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
        memset(dp,0,sizeof dp);
        memset(pre,0,sizeof pre);
        memset(sum,0,sizeof sum);
        for (i=1;i<=n;i++){
            for (j=0;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                sum[i][j]=sum[i-1][j];
                pre[i][j]=0;
            }
            for (j=b[i];j<=m;j++)
                if (dp[i-1][j-b[i]]+a[i]>dp[i][j]||dp[i-1][j-b[i]]+a[i]==dp[i][j]&&sum[i-1][j-b[i]]+i<sum[i][j]
                        ||dp[i-1][j-b[i]]+a[i]==dp[i][j]&&sum[i-1][j-b[i]]+i==sum[i][j]&&calc(i-1,j-b[i],i,j)) {
                    dp[i][j]=dp[i-1][j-b[i]]+a[i];
                    sum[i][j]=sum[i-1][j-b[i]]+i;
                    pre[i][j]=1;
                }
        }
        int ans=0;
        for (i=1;i<=m;i++)
            if (dp[n][i]>dp[n][ans]||dp[n][i]==dp[n][ans]&&sum[n][i]<sum[n][ans]||dp[n][i]==dp[n][ans]&&sum[n][i]==sum[n][ans]&&calc(n,i,n,ans))ans=i;
        printf("Case #%d:\n",dc);
        printf("%d %d\n",dp[n][ans],ans);
        Ans[0]=0;
        for (i=n;i;i--)
            if (pre[i][ans]){
                Ans[++Ans[0]]=i;
                ans-=b[i];
            }
        for (i=Ans[0];i>=2;i--)printf("%d ",Ans[i]);
        if (Ans[0])printf("%d\n",Ans[1]);
    }
}