#include<iostream>
#include<cstring>
#include <vector>
#include <map>
#include<algorithm>
using namespace std;
const int MAXN = 200002;
int need[MAXN];
int value[MAXN];
int dp[MAXN];
 
int dpfunc(int* need, int* value, int n, int V)
{
    map<int, vector<int> > seq_data;
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++)
    {
 
        for (int j = V; j >= need[i]; j--) {
            if (dp[j - need[i]] + value[i] > dp[j]) {
                dp[j] = dp[j - need[i]] + value[i];
                vector<int> seq = seq_data[j - need[i]];
                seq.push_back(i);
                seq_data[j] = seq;
            }
        }
 
    }
 
    vector<int> seq1 = seq_data[V];
    int yusuan = 0;
    for (auto itr : seq1) {
        yusuan += need[itr];
    }
 
    cout << dp[V] << " " << yusuan << endl;
 
    vector<int>& seq = seq_data[yusuan];
    int seq_size = seq.size();
    for (auto itr : seq) {
        cout << itr;
        seq_size--;
        if (0 == seq_size) {
            cout << endl;
        }
        else
            cout << " ";
    }
    return 0;
}
 
int main()
{
    int n, V;
    int time;
    cin >> time;
    for (int t = 1; t <= time; ++t) {
        cin >> V >> n;
        memset(need, 0, sizeof(need));
        memset(value, 0, sizeof(value));
        for (int i = 1; i <= n; i++)
        {
            cin >> value[i] >> need[i];
        }
        printf("Case #%d:\n", t);
 
        dpfunc(need, value, n, V);
 
    }
    return 0;
}