#include<iostream>
using namespace std;

int dp[102][102 * 10], cost[102], score[102], path[102];
int ans, n, m, tot;

void print(int num, int sum)
{
    if (num == 1)
    {
        if (dp[num][sum])
            path[++tot] = 1, ans += cost[1];
        return;
    }
    if (dp[num][sum] > dp[num - 1][sum])
    {
        print(num - 1, sum - cost[num]);
        path[++tot] = num, ans += cost[num];
    }
    else
        print(num - 1, sum);
}

int main()
{
    int t, k = 0;
    cin >> t;
    while (++k <= t)
    {
        tot = 0, ans = 0;
        cin >> m >> n;
        for (int i = 1; i <= n; ++i)
            cin >> score[i] >> cost[i];
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j <= m; ++j)
                if (j >= cost[i])
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i]] + score[i]);
                else
                    dp[i][j] = dp[i - 1][j];
        if (n)
            print(n, m);
        cout << "Case #" << k << ":" << endl;
        cout << dp[n][m] << " " << ans << endl;
        if (tot > 0)
        {
            for (int i = 1; i < tot; ++i)
                cout<<path[i]<<" ";
            cout << path[tot] << endl;
        }
    }
    return 0;
}