#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 1e3 + 10;
typedef long long LL;
struct node{
    int v,c;
}st[110];
vector <int> v[MAX];
int dp[MAX],d[MAX];
int main()
{
    int b,n,nl = 0,T,ok = 0;
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&b,&n);
        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n; i++)
            scanf("%d %d",&st[i].v,&st[i].c);
        for(int i = 0; i <= b; i++) v[i].clear();
        for(int i = 1; i <= n; i++)
            for(int j = b; j >= st[i].c;  j--){
                if(dp[j] < dp[j - st[i].c] + st[i].v){
                    dp[j] = dp[j - st[i].c] + st[i].v;
                    v[j] = v[j - st[i].c];
                    v[j].push_back(i);
                }
                else if(dp[j] == dp[j - st[i].c] + st[i].v){
                    int sum = 0,ans = 0,p = j - st[i].c;
                    for(int o = 0; o < v[j].size(); o++)
                        sum += v[j][o];
                    for(int o = 0; o < v[p].size(); o++)
                        ans += v[p][o];
                    if(sum > ans + i)
                        v[j] = v[j - st[i].c],v[j].push_back(i);
                }
            }
        printf("Case #%d:\n",++nl);
        int pl = 0,o = 0;
        for(int i = 0; i < v[b].size(); i++)
            d[++pl] = v[b][i],o += st[v[b][i]].c;
        printf("%d %d\n",dp[b],o);
        if(pl == 0) continue;
        for(int i = 1; i < pl; i++)
            printf("%d ",d[i]);
        printf("%d\n",d[pl]);
    }
    return 0;
}