// 標準入力
var fs = require('fs'),
length = fs.fstatSync(process.stdin.fd).size,
buffer = new Buffer(length),
bytesRead = fs.readSync(process.stdin.fd, buffer, 0, length, 0),
input = buffer.toString('utf8', 0, bytesRead).split('\n');
main();

function main(){
  var read = 0;
  var resultCase = 1;
  while(true){
    var maxWeight = +input[read++];
    if(!maxWeight){
      break;
    }
    
    var treasures = +input[read++];

    // dp[宝][重さ] = 価値
    var dp = new Array(treasures);
    dp[0] = new Int32Array(maxWeight);

    var resultWeight = 1001;
    var resultCost = 0;

    for(var i = 1; i <= treasures; i++){
      var c = input[read++].split(",");
      var tv = +c[0];
      var tw = c[1] - 1; // to index

      dp[i] = new Int32Array(maxWeight);
      
      for(var w = tw; w < maxWeight; w++){
        var dpw = dp[i][w] = max(dp[i-1][w-tw] + tv, dp[i-1][w]);
        
        if(dpw > resultCost){
          resultCost = dpw;
          resultWeight = w;
        }

      }
    }


    console.log("Case " + resultCase++ + ":\n" + resultCost + "\n" + ++resultWeight);

  }
}

function max(a, b) {
  var t = a - b;
  return a - (t & (t >> 31));
}