n = 0
until gets == "0"
    n += 1
    w = $_.to_i
    
    a = []
    #possible[??????] => ??????
    possible = {}
    possible[0] = 0
    
    gets.to_i.times{|i|
    	price,weight = gets.split(',').map &:to_i
    	temp = {}
    	possible.each{|key,value|
    		#???????????£??????????????§?????????????????????????????\?????????
    		if value + weight <= w
    			if possible[key+price]
    				temp[key+price] = [value + weight, possible[key+price]].min
    			else
    				temp[key+price] = value + weight
    			end
    		end
    	}
    	temp.each{|key,value|
    	    possible[key] = value
    	}
    }
    puts "Case #{n}:"
    puts possible.max[0]
    puts possible.max[1]
end
    
    