#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1e6;
const int inf = 0x3f3f3f3f;
typedef pair<int , int> P;
int W, dp[1005][1005], T, B, N, w[1005], v[1005], s, t, tag[1005][1005];
vector<int > ans;
int d[maxn], d_re[maxn], inq[maxn];
struct edge{
    int to, w, nxt;
}e[4 * maxn], e_re[4 * maxn];
int head[maxn], head_re[maxn],id;

void add_edge(int u, int v, int w){
    id++;
    e[id].to = v; e[id].w = w; e[id].nxt = head[u];
    head[u] = id;
    e_re[id].to = u; e_re[id].w = w; e_re[id].nxt = head_re[v];
    head_re[v] = id;
}

int f(int i, int j){
    return i * (B + 1) + j;
}


void init(){
    ans.clear();
    W = 0;
    memset(tag, 0, sizeof(tag));
    cin >> B >> N;
    for(int i = 1; i <= N; ++i){
        cin >> v[i] >> w[i];
    }
    id = 0;
    for(int i = 0; i < N* (B + 1) + B + 10; ++i) head[i] = 0, head_re[i] = 0;
}
void DP(){
    dp[0][0] = 0;
    for(int i = 1; i <= N; ++i){
        for(int j = 0; j <= B; ++j){
            dp[i][j] = dp[i - 1][j];
            if(j >= w[i] && dp[i - 1][j - w[i]] + v[i] >= dp[i][j]){
                dp[i][j] = dp[i - 1][j - w[i]] + v[i];
            }
            if(dp[i][j] == dp[i - 1][j - w[i]] + v[i]){
                add_edge(f(i - 1, j - w[i]), f(i, j), i);
            }
            if(dp[i][j] == dp[i - 1][j]){
                add_edge(f(i - 1, j), f(i, j), 0);
            }
        }
    }
    s = f(N , B + 1);
    t = f(N, B);
    for(int i = 0; i <= B; ++i){
        add_edge(s, f(0, i), 0);
    }
}
void spfa(){
    memset(d, inf, sizeof(d));
    queue<int > Q;
    Q.push(s), d[s] = 0; inq[s] = 1;
    while (Q.size()){
        int u = Q.front(); Q.pop(); inq[u] = 0;
        for(int p = head[u]; p; p = e[p].nxt){
            int to = e[p].to;
            if(d[to] > d[u] + e[p].w){
                d[to] = d[u] + e[p].w;
                if(!inq[to]){
                    Q.push(to); inq[to] = 1;
                }
            }
        }
    }
}
void spfa_re(){
    memset(d_re, inf, sizeof(d_re));
    queue<int > Q;
    Q.push(t), d_re[t] = 0; inq[t] = 1;
    while (Q.size()){
        int u = Q.front(); Q.pop(); inq[u] = 0;
        for(int p = head_re[u]; p; p = e_re[p].nxt){
            int to = e_re[p].to;
            if(d_re[to] > d_re[u] + e_re[p].w){
                d_re[to] = d_re[u] + e_re[p].w;
                if(!inq[to]){
                    Q.push(to); inq[to] = 1;
                }
            }
        }
    }
}
void dfs(int i, int j){
    if(i == 0) return;
    if(j >= w[i] && v[i] > 0){
        if(tag[i - 1][j - w[i]] == 2){
            ans.push_back(i);
            W += w[i];
            dfs(i - 1, j - w[i]);
            return;
        }
    }
    dfs(i - 1, j);
}
void Find_path( ){
    for(int i = 0; i <= N; ++i){
        for(int j = 0; j <= B; ++j){
            if(d[f(i, j)] + d_re[f(i, j)] == d[t]) tag[i][j] = 1;
        }
    }
    queue<int> que;
    for(int i = 0; i <= B; ++i){
        if(tag[0][i]){
            que.push(i);
        }
    } 
    for(int col = 0; col <= N; ++col){
        vector<int > vec;
        vec.clear();
        while(que.size()){
            int p = que.front(); que.pop();
            tag[col][p] = 2;
            vec.push_back(p);
        }
        for(int i = 0; i < vec.size(); ++i){
            int p = vec[i];
            if(tag[col + 1][p + w[col + 1]] == 1){
                que.push(p + w[col + 1]);
            }
        }
        if(que.size() == 0){
            for(int i = 0; i < vec.size(); ++i){
                int p = vec[i];
                if(tag[col + 1][p] == 1){
                    que.push(p);
                }
            }
        }
    }
    if(tag[N][B] == 2){
        dfs(N, B);
    }
}
int main(){
    cin >> T;
    for(int t = 1; t <= T; ++t){
        init();
        DP();
        spfa();
        spfa_re();
        Find_path();
        /*for(int i = 0; i <= N; ++i){
            for(int j = 0; j <= B; ++j){
                cout << tag[i][j] << " ";
            }
            cout << endl;
        }*/
        cout << "Case #" << t << ":\n";
        cout << dp[N][B] << " " <<W << endl; 
        if(ans.size()){
            cout << ans[ans.size() - 1];
            for(int i = ans.size() - 2; i >= 0; --i){
                cout << " " << ans[i];
            }
            cout << "\n";
        }
    } 
    return 0;
}