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

int main(){
   int n,W;
   int w[1000],v[1000];
   int i,l,z,count=1,Max;
   int dp[2][1001];
   string Case = "Case ";
   char s;
   
   for(;;){
      cin>>W;
      if(W==0) break;
      
      cin>>n;
      for(i=0;i<n;i++) cin>>v[i]>>s>>w[i];
      
      memset(dp,0,sizeof(dp));
      Max=0;
      
      for(i=1;i<=n;i++){
         for(l=1;l<=W;l++){
            if(w[i]>l)
               dp[1][l] = dp[0][l];
            else{
               dp[1][l] = max(dp[0][l],dp[0][l-w[i]]+v[i]);
            }
         }
         for(z=0;z<=W;z++) dp[0][z]=dp[1][z];
         
         memset(dp[1],0,sizeof(dp[1]));
      }
      for(i=W-1;i>=0;i--){
         if(dp[0][i+1]==dp[0][i])
            continue;
         else{
            Max=i+1;
            break;
         }
      }
      
      cout<<Case<<count<<":"<<endl;
      cout<<dp[0][W]<<endl;
      cout<<Max<<endl;
      count++;
   }
   return 0;
}