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

//関数の宣言
int main();
int rec();
void slove();

//グローバル変数
int n,ww,c=0,omo=0,a=0;
int w[11111],v[11111];
int dp[11111][11111];//メモ化テーブル

int main(){ //入力

  while(1){
  scanf("%d",&ww);
  if(ww==0) break;
  c++;
  omo=0;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d,%d",&v[i],&w[i]);
      }
  slove();
  }
  return 0;
}

int rec(int i,int j){
  if(omo<w[i]){
    omo=w[i];
  }
  //既に調べたことがあるならその結果を再利用
  if(dp[i][j]>=0){
    return dp[i][j];
  }
  int res;

  if(i==n){
    res=0;
  }
  else if(j<w[i]){
    res=(i+1,j); 
  }
  else{
      res=max(rec(i+1,j),rec(i+1,j-w[i])+v[i]);
    }
    //結果をテーブルに記憶する
   return dp[i][j]=res;
}

void slove(){
  //まだ調べていないことを表す-1でメモ化テーブルを初期化
  memset(dp,-1,sizeof(dp));
  printf("Case %d:\n",c);
  printf("%d\n",rec(0,ww));
  printf("%d\n",omo);
}