num = 1
while true
  w = gets().to_i
  break if w==0
  n = gets().to_i
  v = []
  h = []
  n.times do |i|
    v[i],h[i] = gets().split(",").map(&:to_i)
  end
  dp = Array.new(n){Array.new(w+1,0)}
  n.times do |i|
   (1+w).times do |j|
     if h[i] > j
       dp[i][j] = dp[i-1][j]
     else
       dp[i][j] = [dp[i-1][j],dp[i-1][j-h[i]]+v[i]].max
     end
   end
  end
  weight = (0..w).map.select{|x| dp[n-1][x] == dp[n-1][w]}.min
  puts "Case #{num}:"
  puts dp[n-1][w]
  puts weight
  num += 1
end