#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 110,M = 1010;
int dp[N][M] = {0};
int score[N] = {0};
int price[N] = {0};

int main(){
    int T;
    cin>>T;
    int count = 1;
    while(count <= T)
    {
        int money;
        cin>>money;
        int n;
        cin>>n;
        for(int i = 1;i <= n;i ++)
        {
            cin>>score[i]>>price[i];
        }
        for(int i = 1;i <= n ;i ++)
        {
            for(int j = 0;j <= money;j ++)
            {
                dp[i][j] = dp[i - 1][j];
                if(j >= price[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - price[i]] + score[i]);
            }
        }
        cout<<"Case #"<<count<<":"<<endl;
        cout<<dp[n][money]<<" ";
        int sum = 0;
        vector<int> ans;
        for(int i = n;i;i --)
        {
            if(dp[i][money] > dp[i - 1][money] && money >= price[i])
            {
                ans.push_back(i);
                money -= price[i];
                sum += price[i];
            }
        }
        cout<<sum<<endl;
        sort(ans.begin(),ans.end());
        for(int i = 0;i < ans.size();i ++)
        {
            if(i) cout<<" ";
            cout<<ans[i];
        }
        if(!ans.empty()) cout<<endl;
        count ++;
    }
    return 0;
}