//A Thief
#include <cstdio>
#include <iostream>
#include <string.h>
#include <cstdlib>

using namespace std;

int dp[2000][2000];
int n;
int w[2000], v[20000];
int W;
int 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{
		if(rec(i + 1, j) < rec(i + 1, j - w[i]) + v[i]){
			res = rec(i + 1, j - w[i]) + v[i];
			weight += w[i];
		}
		else{
			res = rec(i + 1, j);
			weight -= w[i];
		}
	}
	return dp[i][j] = res;
}

void solve()
{
	memset(dp, -1, sizeof(dp));
	cout << rec(0, W) << endl;
}

int main()
{
	int count = 1;
	while(scanf("%d", &W) != EOF){
		if(W == 0){ break; }
		char c;
		char temp[10000];
		cin >> n;
		for(int i = 0; i < n; i++){
			scanf("%d,%d", &v[i], &w[i]);
		}
		weight = 0;
		cout << "Case " << count << ":" << endl;
		solve();
		cout << weight << endl;
		count++;
	}
	
	return 0;
}