#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <vector>
#include <stack>
#include <algorithm>
#include <bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,n) for(int i=a; i<n; i++)
#define rep1(i,a,n) for(int i=n-1; i>=a; i--)
#define sd(a) scanf("%d",&a)
#define sll(a) scanf("%lld",&a)
#define test(a) cout<<a<<endl
#define test2(a,b) cout<<a<<" "<<b<<endl
#define IOS ios::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef  long long ll;
const int MAX = 1e6+10;
const int N = 1e4+10;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e7+7;
const double pi=3.1415926535898;
const double eps=1e-9;
const int MAXN = 1e5+10;

struct DP{
    int score;
    int num;
    int cost;
    vector<int> G;
}dp[110][1010];

struct food{
    int cost;
    int score;
}a[110];

int casen = 1;
void solve(){
    int B, N;
    sd(B);
    sd(N);
    for(int i = 1; i <= N; ++i){
        sd(a[i].score);
        sd(a[i].cost);
    }
    for(int i = 0; i <= B; ++i){
        dp[0][i].score = 0;
        dp[0][i].num = 0;
        dp[0][i].G.clear();
    }

    for(int i = 1; i <= N; ++i){
            for(int j = 0; j <= B; ++j){
                dp[i][j] = dp[i-1][j];
            }
        for(int j = 0; j <= B; ++j){
            if(dp[i-1][j].cost!=j) continue;
            if(j + a[i].cost <= B){
//                dp[i][j + a[i].cost] = dp[i-1][j + a[i].cost];
                if(dp[i-1][j].score + a[i].score > dp[i][j + a[i].cost].score){
                    dp[i][j+a[i].cost] = dp[i-1][j];
                    dp[i][j+a[i].cost].score += a[i].score;
                    dp[i][j+a[i].cost].cost += a[i].cost;
                    dp[i][j+a[i].cost].num += i;
                    dp[i][j+a[i].cost].G.push_back(i);

                }
                else if(dp[i-1][j].score + a[i].score == dp[i][j + a[i].cost].score){
                    if(dp[i-1][j].num + i < dp[i][j + a[i].cost].num){
                        dp[i][j+a[i].cost] = dp[i-1][j];
                        dp[i][j+a[i].cost].score += a[i].score;
                        dp[i][j+a[i].cost].cost += a[i].cost;
                        dp[i][j+a[i].cost].num += i;
                        dp[i][j+a[i].cost].G.push_back(i);
                    }
                    else if(dp[i-1][j].num + i == dp[i][j + a[i].cost].num){
                        int flag = 0;
                        for(int k = 0; k < min(dp[i-1][j].G.size(),dp[i][j + a[i].cost].G.size()); ++k){
                            if(dp[i-1][j].G[k] < dp[i][j + a[i].cost].G[k]){
                                flag = -1;
                                break;
                            }
                            else if(dp[i-1][j].G[k] > dp[i][j + a[i].cost].G[k]){
                                flag = 1;
                                break;
                            }
                        }
                        if(flag == -1){
                            dp[i][j+a[i].cost] = dp[i-1][j];
                            dp[i][j+a[i].cost].score += a[i].score;
                            dp[i][j+a[i].cost].cost += a[i].cost;
                            dp[i][j+a[i].cost].num += i;
                            dp[i][j+a[i].cost].G.push_back(i);
                        }
                        else if(flag == 0){
                            if(dp[i][j + a[i].cost].G.size() > dp[i-1][j].G.size()){
                                if(i < dp[i][j + a[i].cost].G[dp[i-1][j].G.size()]){
                                    dp[i][j+a[i].cost] = dp[i-1][j];
                                    dp[i][j+a[i].cost].score += a[i].score;
                                    dp[i][j+a[i].cost].cost += a[i].cost;
                                    dp[i][j+a[i].cost].num += i;
                                    dp[i][j+a[i].cost].G.push_back(i);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    DP ans;
    ans.score = 0;
    ans.num = inf;
    for(int i = 0; i <= B; ++i){
        if(dp[N][i].score > ans.score){
            ans = dp[N][i];
        }
        else if(dp[N][i].score == ans.score){
            if(dp[N][i].num < ans.num){
                ans = dp[N][i];
            }
            else if(dp[N][i].num == ans.num){
                int flag = 0;
                for(int j = 0; j < min(ans.G.size(), dp[N][i].G.size()); ++j){
                    if(ans.G[j] < dp[N][i].G[j]){
                        flag = -1;
                    }
                    else if(ans.G[j] > dp[N][i].G[j]){
                        flag = 1;
                    }
                }
                if(flag == 0){
                    if(ans.G.size() > dp[N][i].G.size()){
                        flag = 1;
                    }
                }
                if(flag == 1){
                    ans = dp[N][i];
                }
            }
        }
    }
    printf("Case #%d:\n", casen++);
    if(ans.score > 0){
        printf("%d %d\n", ans.score, ans.cost);
        for(int i = 0; i < ans.G.size(); ++i){
            printf("%d", ans.G[i]);
            if(i!=ans.G.size()-1) putchar(' ');
        }
        printf("\n");
    }
    else{
        printf("0 0\n");
    }

}


int main(){
#ifdef local
    freopen("in","r",stdin);
#endif
    int t;
    sd(t);
    while(t--){
        solve();
    }

    return 0;
}