#include<iostream>
using namespace std;
int max(int n,int m){
  return(n>m?n:m);
}
int main(){
  int nap; //重さ
  int n;//お宝の数
  int c = 1;
  int ans = 0;
  int ans2 = 0;
  int mv = 0; //最大の重さ
  int cach; //価値の合計
  while(cin>>nap){
    if(nap==0) break;
    cin >> n;
  int so[nap+1]; //総数
  int kach[n]; //価値
  int val[n]; //重さ
  char a;
  for(int i=1;i<=nap;i++){ 
    so[i] = -1;
    so[0] = 0;
  }
  for(int i=0;i<n;i++){
    cin >> kach[i] >> a >> val[i];
    mv = nap - val[i];
    for(int j=mv;j>=0;j--){
      if(so[j]!=-1){
	cach = kach[i] + so[j];
	so[val[i]+j] = max(so[val[i]+j],cach);
      }
    }
  }
  for(int i=0;i<=nap;i++){
    if(ans<so[i]){
      ans = so[i];
      ans2 = i;
    }
}    
  cout << "Case " << c++ << ':' << endl;
  cout << ans << endl << ans2 << endl;
  ans = 0;
  ans2 = 0;
}
  return 0;
}