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

int main()
{
	int w, n, i, j, cs, val[1001], wg[1001], dp[1001], inserted[1001];
	cs = 1;
	
	while( cin >> w , w)
	{
		memset( dp, 0, sizeof(dp));
		memset( val, 0, sizeof(val));
		memset( wg, 0, sizeof(wg));
		memset( inserted, 0, sizeof(inserted));
		
		inserted[0] = 1;
		
		cin >> n;
		
		for( i = 1; i <= n; i++)
		{	
			char c;
			cin >> val[i] >> c >> wg[i];
		}
		
		
		for( j = 1; j <= n; j++)
			for( i = 0; i <= w; i++)
				if( inserted[i] && i+wg[j] <= w && dp[i+wg[j]] < dp[i] + val[j] )
				{
						dp[i+wg[j]] = max( dp[i] + val[j], dp[i+wg[j]] );
						
						inserted[i+wg[j]] = 1;
						
						i = (i+wg[j]) + 1;
				}
		
		for( i = w; i > 0; i--)
		{
			if( dp[i] > dp[i-1] )
			{
				cout << "case " << cs << ":" << endl;
				cout << dp[i] << endl;
				cout << i << endl;
				cs++;
				break;
			}
		}
		
	}
	
	return 0;
}