@num = 1
loop do
  w = gets.to_i
  break if w == 0
  n = gets.to_i
  arr = n.times.map { gets.split(',').map(&:to_i) }

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

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