#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#define X first
#define Y second
#define clr(u,v); memset(u,v,sizeof(u));
#define in() freopen("data","r",stdin);
#define out() freopen("ans","w",stdout);
#define Clear(Q); while (!Q.empty()) Q.pop();
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
const int INF = 0x3f3f3f3f;
int dp[maxn][110];
//struct node
//{
//    int x,y;
//}to[maxn][110];
vector <int> ans;
vector <short> to2[maxn][110];
//char str1[100000],str2[100000];
//int cnt1=0,cnt2=0;
bool Smaller(vector <short> &A, vector <short> &B)
{
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < A.size(); i++) sum1 += A[i];
    for (int i = 0; i < B.size(); i++) sum2 += B[i];
    if (sum1 != sum2)
    {
        return sum1 < sum2;
    }
    int Mx = max(A.size(), B.size());
    for (int i = 0; i < Mx; i++)
    {
        int a = i >= A.size() ? 0 : A[i];
        int b = i >= B.size() ? 0 : B[i];
        if (a < b) return 1;
        else if (a > b) return 0;
    }
    return 0;
//    cnt1=0;
//    cnt2=0;
//    for (int i=0;i<A.size();i++)
//    {
//        int num = A[i];
//        while (num>0)
//        {
//            str1[cnt1++]=num%10+'0';
//            num/=10;
//        }
//        str1[cnt1++]=' ';
//    }
//    str1[cnt1]='\0';
//    for (int i=0;i<B.size();i++)
//    {
//        int num = B[i];
//        while (num>0)
//        {
//            str2[cnt2++]=num%10+'0';
//            num/=10;
//        }
//        str2[cnt2++]=' ';
//    }
//    str2[cnt1]='\0';
////    cout << str1 << endl;
////    cout << str2 << endl;
//    if (strcmp(str1,str2)<0) return 1;
    return 0;
}
int main()
{
#ifdef LOCAL
    in();
#endif
    int T;
    scanf("%d", &T);
    for (int c = 1; c <= T; c++)
    {
        clr(dp, 0);
        int n, cost, score, allmoney;
        scanf("%d%d", &allmoney, &n);
        for (int j = allmoney; j >= 0; j--)
            for (int k = n; k >= 0; k--)
//                    to[j][k].x=to[j][k].y=-1,;
                to2[j][k].clear();

        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d", &score, &cost);
            for (int j = allmoney; j >= cost; j--)
                for (int k = n; k >= 1; k--)
                    if (dp[j][k] < dp[j-cost][k-1] + score)
                    {
                        dp[j][k] = dp[j-cost][k-1] + score;
//                        to[j][k].x=j-cost;
//                        to[j][k].y=k-1;
                        to2[j][k] = to2[j-cost][k-1];
                        to2[j][k].pb(i);
                    }
                    else if (dp[j][k] == dp[j-cost][k-1] + score)
                    {
                        vector <short> temp;
                        temp.clear();
                        temp = to2[j-cost][k-1];
                        temp.pb(i);
                        if (Smaller(temp,to2[i][j]))
                        {
                            to2[i][j]=temp;
                        }
                    }
        }
        int Mx = -1;
        pii pos;
//        for (int i = 0; i <= allmoney; i++)
//        {
//            for (int j = 0; j <= allid; j++)
//                printf("%d ", dp[i][j]);
//            puts("");
//        }
        for (int i = 0; i <= allmoney; i++)
            for (int j = 0; j <= n; j++)
                if (Mx < dp[i][j])
                {
                    Mx = dp[i][j];
                    pos = make_pair(i, j);
//                    int sum1 = 0;
//                    for (int k = 0; k < to2[i][j].size(); k++)
//                        sum1 += to2[i][j][k];
//                    sum = sum1;
                }
                else if (dp[i][j] == Mx)
                {
                    if (Smaller(to2[i][j], to2[pos.X][pos.Y]))
                    {
//                        sum = sum1;
                        Mx = dp[i][j];
                        pos = make_pair(i, j);
                    }
                }

        printf("Case #%d:\n", c);
        printf("%d %d\n", Mx, pos.X);
        for (int i = 0; i < to2[pos.X][pos.Y].size(); i++)
            printf("%d%c", to2[pos.X][pos.Y][i],i== to2[pos.X][pos.Y].size()-1?'\n':' ');
//        if (to2[pos.X][pos.Y].size())
//        puts("");
//        ans.clear();
//        while (pos.X!=-1)
//        {
//            int tx=pos.X,ty=pos.Y;
////            printf("pos %d %d %d\n",tx,ty,to[tx][ty].num);
//            ans.pb(ty-to[tx][ty].y);
//            pos.X=to[tx][ty].x;
//            pos.Y=to[tx][ty].y;
//        }
//        for (int i=ans.size()-1;i>=0;i--)
//        printf("%d ",ans[i]);
//        puts("");
//
//        for (int i = 0; i < to2[pos.X][pos.Y].size(); i++)
//            printf("%d ", to2[pos.X][pos.Y][i]);
//        puts("");

    }
    return 0;
}