#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int score[105], cost[105], dp[1005], visted[105];
bool vis[105][1005];

int main(){
    int T, kase = 0, sumcost, len;
    scanf("%d", &T);
    while(T--){
        int B, N, maxscore = -1, mincost = 1001, t;
        scanf("%d%d", &B, &N);
        for(int i = 1; i <= N; i++) 
            scanf("%d%d", &score[i], &cost[i]);
        memset(dp, 0, sizeof(dp));
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= N; i++){
            for(int j = B; j >= cost[i]; j--){
                if(dp[j-cost[i]]+score[i] > dp[j]){
                    dp[j] = dp[j-cost[i]]+score[i];
                    vis[i][j] = 1;
                }
            }
        }
        sumcost = len = 0;
        for(int i = N, j = B; i > 0; i--){
            if(vis[i][j]){
                sumcost += cost[i];
                j -= cost[i];
                visted[len++] = i;
            }
        }
        sort(visted, visted+len);
        printf("Case #%d:\n%d %d\n", ++kase, dp[B], sumcost);
        if(len != 0){
            printf("%d", visted[0]);
            for(int i = 1; i < len; i++){
                printf(" %d", visted[i]);
            }
            puts("");
        }
    }
    return 0;
}