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

  mw, mv = w, 0
  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?
        [wi, wi + p[1]].each do |tw|
          if tw <= w
            dp[[i, tw]] = [dp[[i, tw]]||0, dp[[i-1, wi]] + (tw != wi ? p[0] : 0)].max
            mw, mv = [tw, dp[[i, tw]]] if ( dp[[i, tw]] > mv || ( dp[[i, tw]] == mv && tw < mw ) )
          end
        end
      end
    end
  end

  puts "Case #{c}:"
  puts mv
  puts mw

  c += 1
end