#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>

using namespace std;

vector< vector<int> > dp;
vector<int> w,v;
int n,weight;

int rec(int i,int j){

	if(dp[i][j]>=0) return dp[i][j];

	int res;
	if(i==n) res=0;
	else if(j<w[i]) res=rec(i+1,j);
	else res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);

	return dp[i][j]=res;
}

int main(){

	int count=1;
	cin>>weight;
	while(weight!=0){
		cin>>n;
		w.resize(n); v.resize(n);
		for(int i=0;i<n;i++) scanf("%d,%d",&v[i],&w[i]);

		dp = vector< vector<int> >(n+1);
		for(int i=0;i<n+1;i++) dp[i]=vector<int>(weight+1,-1);

		int ans_v=rec(0,weight);
		cout<<"Case "<<count<<":"<<endl<<ans_v<<endl;
	
		weight--;
		while(weight){
			dp = vector< vector<int> >(n+1);
			for(int i=0;i<n+1;i++) dp[i]=vector<int>(weight+1,-1);
			if(ans_v!=rec(0,weight)) break;
			weight--;
		}
		cout<<weight+1<<endl;

		count++;
		cin>>weight;

	}


	return 0;

}