n = 0
until gets.to_i == 0
	n += 1
	maxweight = $_.to_i
	
	a = []
	possible = Array.new(maxweight+1,nil)
	possible[0] = 0
	
	gets.to_i.times{|i|
		temp = Array.new(maxweight+1,nil)
		price,weight = gets.split(',').map &:to_i
		(maxweight+1).times{|j|
			if possible[j]
				temp[j+weight] = possible[j] + price
				possible[j] = [possible[j],temp[j].to_i].max
			else
			    possible[j] = temp[j]
			end
		}
	}
	puts "Case #{n}:"
	puts a = possible[0..maxweight].map(&:to_i).max
	puts possible.index(a)
end