#include <stdio.h>
#include <string.h>
#define N 1005
int dp[N];
bool path[110][N];
int a[110], b[110];
int ans[110];
int main(){
    int t, m, n;
    int cas = 0;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &m, &n);
        for(int i = 1; i <= n; i++)
            scanf("%d%d", &a[i], &b[i]);
        memset(dp, 0, sizeof(dp));
        memset(path, false, sizeof(path));
        for(int i = 1; i <= n; i++){
            for(int j = m; j >= b[i]; j--){
                if(dp[j] < dp[j-b[i]] + a[i]){
                    dp[j] = dp[j-b[i]] + a[i];
                    path[i][j] = true;
                }
            }
        }
        printf("Case #%d:\n", ++cas);
        int v = m, sum = 0, index = 0;
        for(int i = n; i >= 1 && v >= 0; i--){
            if(path[i][v]){
                ans[index++] = i;
                sum += b[i];
                v -= b[i];
            }
        }
        printf("%d %d\n", dp[m], sum);
        if(index == 0)continue;
        for(int i = index-1; i > 0; i--)
            printf("%d ", ans[i]);
        printf("%d\n", ans[0]);
    }
    return 0;
}