#include<iostream>


using namespace std;

int value[1000][1000];

int main () {

	int count = 1;
	while ( true ) {

		int w, n;

		cin >> w;
		if ( w == 0 )
			break;
		cin >> n;

		for ( int i=0; i<n;i ++ ) {
			for ( int j=0; j<1000; j++ ) {

				value[i][j] = 0;

			}
		}


		int maxv, minw;

		maxv =0;
		minw = 100000;

		for ( int i=0; i<n; i++ ) {
			int v, ow;
			char ch;

			cin >> v >> ch >> ow;

			value[0][ow] = v;

			if ( maxv <= v ) {
				if ( maxv < v ) {
					maxv = v;
				}
				if (minw > ow ) {
					minw = ow;
				}
			}

		}
	

		for ( int i=0; i<n-1; i++ ) {
			for ( int j=0; j<1000; j++ ) {
				if ( value[i][j] != 0 ) {

					//value[i+1][j] = value[i][j];

					for ( int k=j+1; k<1000; k++ ) {
						if ( value[i][k] != 0 ) {
							if ( j+k < w && 2*(i+1)-1< n) {
								if ( value[2*(i+1)][k+j] < value[i][j] + value[i][k] ) {
									value[2*(i+1)][k+j] = value[i][j] + value[i][k];

									if ( maxv <= value[2*(i+1)][k+j] ) {
										if ( maxv < value[2*(i+1)][k+j] ) {
											maxv = value[2*(i+1)][k+j];
											minw = j+k;
										}
										else if (minw > j+k ) {
											minw = j+k;
										}
									}
								}
							}
						}
					}
				}
			}
		}
/*
		cout << endl;
		for ( int i=0 ;i<1000; i++ ) {
			for ( int j=0; j<n; j++ ) {
				cout << value[j][i] << "\t";
			}
			cout << endl;
		}
		cout << endl << endl;
*/

		cout << "Case " << count << ":" << endl;
		cout << maxv << endl << minw << endl << endl;

	}
}