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

int main(){
  int W,n,ans,count=1,weight,v[1001],w[1001];
  int dp[2][1000];
  
  while(cin>>W,W){
    fill(v,v+1001,0);
    fill(w,w+1001,0);
    fill(dp[0],dp[2],0);
    ans=0;
    
    cin>>n;
    for(int i=0;i<n;i++){
      cin>>v[i];
      getchar();
      cin>>w[i];
    }
    
    for(int i=0;i<n;i++){
      for(int l=1;l<=W;l++){
        if(w[i]<=l)
          dp[1][l]=max(dp[0][l],dp[0][l-w[i]]+v[i]);
        else
          dp[1][l]=dp[0][l];
      }
      for(int z=0;z<=W;z++){
        dp[0][z]=dp[1][z];
        dp[1][z]=0;
      }
    }
    
    for(int i=0;i<=W;i++)
      if(dp[0][i]>ans){
        ans=dp[0][i];
        weight=i;
      }
    
    printf("Case %d:\n",count);
    printf("%d\n%d\n",ans,weight);
    count++;
  }
  return 0;
}