#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];
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;
vis[k][j] = true;
} else
continue;
}
}
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;
}
