#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
using namespace std;

struct Treasure{
	int Weight;
	int Worth;
};
vector<int> TempMaxWorth;

int GetMaxWorth(const int MaxWeight,vector<Treasure> nowTreasureCollection, vector<Treasure>::iterator nowIterator,const vector<Treasure>& AllTreasureCollection){
	vector<Treasure>::iterator rootIterator(nowIterator);
	for (; nowIterator!=AllTreasureCollection.end(); ++nowIterator){
		nowTreasureCollection.push_back(*(nowIterator));
		const int NowWorth = accumulate(nowTreasureCollection.cbegin(),
			nowTreasureCollection.cend(),
			0,
			[](const int q, const Treasure& p){return q + p.Worth; }
		);
		const int NowWeight = accumulate(nowTreasureCollection.cbegin(),
			nowTreasureCollection.cend(),
			0,
			[](const int q, const Treasure& p){return q + p.Weight; });
		if (NowWeight <= MaxWeight&&NowWorth > TempMaxWorth[NowWeight]){
			TempMaxWorth[NowWeight] = NowWorth;
			replace_if(TempMaxWorth.begin() + NowWeight, TempMaxWorth.end(), [=](int n){return NowWorth > n; }, NowWorth);
			if((nowIterator+1)!=AllTreasureCollection.end())GetMaxWorth(MaxWeight, nowTreasureCollection, nowIterator+1,AllTreasureCollection);
		}
		nowTreasureCollection.pop_back();
	}
	nowIterator = (rootIterator);
	return 0;
}

int main(){
	int MaxWeight;
	int TreasureNum;
	for (int i = 1; cin >> MaxWeight;++i){
		if (MaxWeight == 0)return 0;
		cin  >> TreasureNum;
		TempMaxWorth.resize(MaxWeight + 1);
		fill(TempMaxWorth.begin(), TempMaxWorth.end(), 0);
		vector<Treasure> AllTreasureCollection;
		for (int j = 0; j < TreasureNum; ++j){
			Treasure T;
			cin >> T.Worth;
			cin.get();
			cin >> T.Weight;
			AllTreasureCollection.push_back(T);
		}	
		vector<Treasure> NowTreasureCollection = {};
		GetMaxWorth(MaxWeight, NowTreasureCollection, AllTreasureCollection.begin(), AllTreasureCollection);
		cout << "Case " << i << ":" << endl << TempMaxWorth[MaxWeight] << endl << find(TempMaxWorth.cbegin(), TempMaxWorth.cend(), TempMaxWorth[MaxWeight]) - TempMaxWorth.cbegin() << endl;
	}
	return 0;
}