#include<iostream>
#include<memory.h>
#include<algorithm>
using namespace std;
int main()
{
	int W,n,c=0;
	int w,v;
	int dp[1001][1001];
	while (1){
		cin >> W;
		if (W == 0)break;
		c++;
		cin >> n;
		for (int i = 1; i <= n; i++){
			cin >> v >> w;
			for (int i2 = 0; i2 <= W; i2++){
				if (i2 < w)
					dp[i][i2] = dp[i - 1][i2];
				else
					dp[i][i2] = max(dp[i - 1][i2], dp[i - 1][i2-w] + v);
			}
		}
		int maxv=0, maxw;
		for (int i = 0; i <= W; i++){
			if (maxv < dp[n][i]){
				maxv = dp[n][i];
				maxw = i;
			}
		}
		cout << "Case" << c << ":" << endl;
		cout << maxv << endl << maxw << endl;
	}
	
}