@num = 1
loop do
  w = gets.to_i
  break if w == 0

  n = gets.to_i
  tab = n.times.map{ gets.chomp.split(',').map(&:to_i) }

  dp = Array.new(n+1){Array.new(w+1)}
  dp[0][0] = 0

  mw, mv = w, 0
  tab.each_with_index do |p, i|
    (0..w).reject{|wi| dp[i][wi].nil? }.each do |wi|
      t = dp[i+1][wi] = [dp[i+1][wi]||0, dp[i][wi]].max
      mw, mv = wi, t if ((t > mv) || (mv == t && mw > wi))
      if wi+p[1] <= w
        t = dp[i+1][wi+p[1]] = [dp[i+1][wi+p[1]]||0, dp[i][wi]+p[0]].max
        mw, mv = (wi+p[1]), t if ((t > mv) || (mv == t && mw > (wi+p[1])))
      end
    end
  end
  puts "Case #{@num}:", mv, mw
  @num += 1
end