class Treasure
  def initialize(value, weight)
    @value = value;
    @weight = weight;
  end
  def getValue
    return @value;
  end
  def getWeight
    return @weight;
  end
end

MAX_BAG_WEIGHT = 1000;
MAX_NUM_TREASURES = 1000;
MAX_VALUE = 10000;
WEIGHT = 0;
VALUE = 1;

#DP
def getMaxValue(bagWeight, treasureArray)
  table = Array.new(bagWeight + 1, 0);
  treasureArray.each{ |t|
    tWeight = t.getWeight;
    tValue = t.getValue;
    bagWeight.step(tWeight, -1) { |w| #bagWeight書き換わってまずくない？
      break if table[w- tWeight] < 0;
      tmp = table[w]
      table[w] = table[w - tWeight] + tValue if tmp < table[w - tWeight] + tValue
    }
  }
  #p table
  return table;
end

def getMinWeightWhenMaxValue(bagWeight, valueTable)
  minWeight = bagWeight;
  maxValue = valueTable.max
  bagWeight.step(1, -1) { |w|
    break if maxValue > valueTable[w];
    minWeight = w;
  }
  return minWeight;
end

#main
caseNumber = 0;
while true
  bagWeight = gets.to_i;
  break if bagWeight == 0;
  numTreasures = gets.to_i;
  treasure = Array.new;
  numTreasures.step(1, -1) {
    input = gets.chomp.split(/\s*,\s*/);
    treasure << Treasure.new(input[0].to_i, input[1].to_i);
  }
  valueTable = getMaxValue(bagWeight, treasure);
  caseNumber += 1
  puts "Case " + caseNumber.to_s + ":";
  puts valueTable.max; #速度落ちる？
  puts getMinWeightWhenMaxValue(bagWeight, valueTable);
end