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

struct treasure{
	int value;
	int weight;
};

bool comp(treasure t1, treasure t2){
	return (t1.weight < t2.weight);
}

int main(){
	int count = 1;
	int w;
	int n;
	char c;
	const int max = 1001;
	int cost[max];
	int best[max];
	while(cin >> w){
		if(w == 0) break;
		for(int i = 0; i < max; i++){
			cost[i] = 0;
			best[i] = 0;
		}
		vector<treasure> vt;
		cin >> n;
		for(int i = 0; i < n; i++){
			treasure t;
			cin >> t.value >> c >> t.weight;
			vt.push_back(t);
		}
		treasure t;
		t.value = -1;
		t.weight = -1;
		vt.push_back(t);
		sort(vt.begin(), vt.end(), comp);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= w; j++){
				if(vt[i].weight <= j ){
					if(cost[j] < cost[j-vt[i].weight] + vt[i].value){
						if(best[j-vt[i].weight] != i){
							cost[j] = cost[j-vt[i].weight] + vt[i].value;
							best[j] = i;
						}else{
							cost[j] = cost[j-vt[i].weight];
							best[j] = best[j-vt[i].weight]; 
						}
					}
				}
			}
		}
		int i = w;
		while(cost[i] == cost[i-1] && i > 1) i--;
		cout << "Case " << count++ << ":" << endl;
		cout << cost[w-1] << endl;
		cout << i << endl;
	}
	return 0;
}