#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>

#define ll (long long)
#define REP(i,n) for(int i = 0;i<(int)n;i++)
#define FOR(i,a,b) for(int i = (a);i < (b);i++)
#define RFOR(i,a,b) for(int i = (a);i>(b);i--)

using namespace std;

/*thief??????*/

int main(void){
    
    /*(x,y) = (??????,??????)*/
    int endurew;
    int number;
    int answer = 0;
    int casecounter = 1;
    while(cin >> endurew,endurew)
    {
        int dp[1002][1002] = {0};
        int w[1002] = {0},v[1002] = {0};
        cin >> number;
        for(int i  =1; i<= number;i++)
            scanf("%d%*c%d",&v[i],&w[i]);
        
        for(int j = 1; j<= number;j++)
            for(int k = 0;k<=endurew;k++)
            {
              if(j == 1 && k>=w[j])
                  dp[j][k] = v[j];
              else if(k >= w[j])
                  dp[j][k] = v[j]+dp[j-1][k-w[j]];
              else
                  dp[j][k] = dp[j-1][k];
                
            }
        int max = 0;
        for(int i = 1;i<=endurew;i++)
        {
            if(max < dp[number][i])
            {
                answer = i;
                max = dp[number][i];
            }
            
        }
        cout << "Case" << casecounter<< ":" << endl << dp[number][answer]<< endl;
        cout << answer << endl;
        casecounter++;
    }
    return 0;
    
}