ii = 1
while max = gets.to_i
  break if max == 0
  puts "Case #{ii}:"
  n = gets.to_i
  v = []
  w = []
  dp = Array.new(n+1){Array.new(max+1){0}}
  n.times{|i|
    v[i], w[i] = gets.split(",").map(&:to_i)
  }
  i = n - 1
  while i >= 0
    j = 0
    while j <= max
      if j < w[i]
        dp[i][j] = dp[i+1][j]
      else
        dp[i][j] = [dp[i+1][j], dp[i+1][j-w[i]] + v[i]].max
      end
      j += 1
    end
    i -= 1
  end
  p dp[0][max]
  p dp[0].index(dp[0][max])
  ii += 1
end