c = 1
loop do
  w = gets.to_i
  break if w == 0
  n = gets.to_i
  table = Array.new
  n.times do
    table << gets.split(',').map(&:to_i)
  end

  dp = Hash.new
  dp[[0, 0]] = 0
  table.each.with_index(1) do |p, i|
    (0..w).each do |wi|
      unless dp[[i-1, wi]].nil?
        #p dp[i-1][w]
        dp[[i, wi]] = [dp[[i, wi]]||0, dp[[i-1, wi]]].max
        dp[[i, wi + p[1]]] = [dp[[i, wi + p[1]]]||0, dp[[i-1, wi]] + p[0]].max if (( wi + p[1] ) <= w)
      end
    end
  end

  k, v = dp.sort{|a, b| (a[1] <=> b[1]) == 0 ? b[0][1] <=> a[0][1] : a[1] <=> b[1]}.last
  puts "Case #{c}:"
  puts v
  puts k[1]

  c += 1
end