#include<stdio.h>  
#include<string.h>  
#define inf 1044266558  
typedef struct  
{  
    int val;  
    int p;  
}Res;  
typedef struct  
{  
    int val;  
    int pre;  
    int sum;  
}Bet;  
Bet dp[105][1005];  
Res s[105];  
int p[105];  
int main(void)  
{  
    int T, V, n, i, j, k, ans, sum, now, ts, cas = 1;  
    scanf("%d", &T);  
    while(T--)  
    {  
        scanf("%d%d", &V, &n);  
        for(i=1;i<=n;i++)  
            scanf("%d%d", &s[i].val, &s[i].p);  
        memset(dp, 62, sizeof(dp));  
        dp[0][0].val = dp[0][0].sum = dp[0][0].pre = 0;  
        for(i=1;i<=n;i++)  
        {  
            for(j=V;j>=s[i].p;j--)  
            {  
                dp[i][j] = dp[i-1][j];  
                if((dp[i][j].val<dp[i-1][j-s[i].p].val+s[i].val || dp[i][j].val==inf) && dp[i-1][j-s[i].p].val<inf)  
                {  
                    dp[i][j].val = dp[i-1][j-s[i].p].val+s[i].val;  
                    dp[i][j].pre = i;  
                    dp[i][j].sum = dp[i-1][j-s[i].p].sum+i;  
                }  
                else if(dp[i][j].val==dp[i-1][j-s[i].p].val+s[i].val)  
                {  
                    if(dp[i][j].sum>dp[i-1][j-s[i].p].sum+i)  
                    {  
                        dp[i][j].pre = i;  
                        dp[i][j].sum = dp[i-1][j-s[i].p].sum+i;  
                    }  
                }  
            }  
            for(;j>=0;j--)  
                dp[i][j] = dp[i-1][j];  
        }  
        ans = sum = -1, k = 0;  
        for(i=V;i>=0;i--)  
        {  
            if(dp[n][i].val<inf && dp[n][i].val>ans)  
                ans = dp[n][i].val, sum = i, ts = dp[n][i].sum;  
            else if(dp[n][i].val==ans)  
            {  
                if(dp[n][i].sum<ts)  
                    sum = i, ts = dp[n][i].sum;  
            }  
        }  
        printf("Case #%d:\n%d %d\n", cas++, ans, sum);  
        now = n;  
        while(dp[now][sum].pre)  
        {  
            p[++k] = dp[now][sum].pre;  
            ts = dp[now][sum].pre;  
            now = ts-1;  
            sum -= s[ts].p;  
        }  
        if(k==0)  
            continue;  
        printf("%d", p[k]);  
        for(i=k-1;i>=1;i--)  
            printf(" %d", p[i]);  
        printf("\n");  
    }  
    return 0;  
}