#include <bits/stdc++.h>  //百度之星1004
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
struct Node{
    int price,sco;
};
Node node[105];
int dp[1005],he[1005];
bool vis[105][1005];
bool ans[105];
int main() {
    int n;
    scanf("%d", &n);
    for (int l = 1; l <= n; l++) {
        int B, N;
        mem(node);
        scanf("%d%d", &B, &N);
        for (int j = 1; j <= N; j++) {
            scanf("%d", &node[j].sco);
            scanf("%d", &node[j].price);
        }
        mem(dp);
        mem(ans);
        memset(vis, false, sizeof(vis));
        for (int k = 1; k <= N; k++) {
            for (int j = B; j >= node[k].price; j--) {
                if (dp[j] < (dp[j - node[k].price] + node[k].sco)) {
                    dp[j] = dp[j - node[k].price] + node[k].sco;
                    he[j]=he[j-node[k].price]+k;
                    vis[k][j] = true;
                } else if(dp[j]==(dp[j-node[k].price]+node[k].sco)){
                    if(he[j]>he[j-node[k].price]+k){
                        he[j]=he[j-node[k].price]+k;
                        vis[k][j]=true;
                    }
                } 
            }
        }
        int p = B, cnt = 0;
        for (int i = N; i >= 1; i--) {
            if (vis[i][p]) {
                ans[i] = true;
                p -= node[i].price;
                cnt++;
            }
        }

        int Ans = 0;
        for (int i = 1; i <= N; i++) {
            if (ans[i])
                Ans += node[i].price;
        }

        printf("Case #%d:\n", l);
        printf("%d %d\n", dp[B], Ans);
        for (int i = 1; i <= N; i++)
            if (ans[i])
                printf("%d%c", i, (--cnt == 0) ? '\n' : ' ');
    }
    return 0;
}