#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include <utility>

using namespace std;


int main(){
	int dp[1000];
	
	int W,N;
	int v[1000],w[1000];
	
	int count=0;
	
	while(cin>>W,W){
		cin>>N;
		count++;
		for(int i=0;i<N;i++){
			scanf("%d,%d",&v[i],&w[i]);
		}
		
		for(int j=0;j<W;j++){
			if(j<w[0]-1){
				dp[j]=0;
			}else{
				dp[j]=v[0];
			}
		}
		
		for(int i=1;i<N;i++){
			for(int j=0;j<W;j++){
				if(j<w[i]-1){
					dp[j]=dp[j];
				}else{
					dp[j]=max(dp[j],dp[j-w[i]+1]+v[i]);
				}
				if(i==N-1)cout<<dp[j]<<" ";
			}
		}
		cout<<endl;
		cout<<"Case "<<count<<":"<<endl;
		cout<<dp[W-1]<<endl;
		int k;
		for(k=W;dp[k-2]==dp[k-1];k--);
		cout<<k<<endl;
	}
	
	
	
	
	return 0;
	
}