l = 1
loop{
  capacity = readline.chomp.to_i
  break if capacity == 0

  treasure_num = readline.chomp.to_i
  weights = []
  values = []
  treasure_num.times{
    v, w = readline.chomp.split(/,/).map{|c| c.to_i}
    values << v
    weights << w
  }

  dp = Array.new(treasure_num){ Array.new(capacity+1){ 0 } }

  (0..treasure_num-1).each{|t|
    (0..capacity).each{|c|
      if c < weights[t]
        dp[t][c] = dp[t-1][c]
      else
        dp[t][c] = [dp[t-1][c], dp[t-1][c-weights[t]]+values[t]].max
      end
    }
  }

  max_value = 0
  max_weight = 0
  dp[treasure_num-1].each_with_index{|v, i|
    if v > max_value
      max_value = v
      max_weight = i
    end
  }
  puts "Case #{l}:\n#{max_value}\n#{max_weight}"
  l += 1
}