class Knapsack
	def initialize(items, budget)
		@items = items.sort_by{|c, v| -v.to_f / c}
		@budget = budget

		@left_value = 0
		@left_cost = 0
		i = 0
		while i < @items.size
			c, v = @items[i]
			break if @left_cost + c > @budget
			@left_cost += c
			@left_value += v
			i += 1
		end

		@l = @r = i
		@states = []
		@lower_bound = @left_value
		@opt_cost = @left_cost 
	end

	def solve
		return @left_value if @left_cost == @budget || @l == @items.size

		@states << [@left_cost, @left_value]
		@states << [@left_cost + @items[@l][0], @left_value + @items[@l][1]]
	
		loop {
			if @r < @items.size - 1
				@r += 1
				@states += @states.map{|c, v|
					[c + @items[@r][0], v + @items[@r][1]]
				}
			end
	
			if @l > 0
				@l -= 1
				@left_cost -= @items[@l][0]
				@left_value -= @items[@l][1]
				@states += @states.map{|c, v|
					[c - @items[@l][0], v - @items[@l][1]]
				}
			end

			prun
			update_lower_bound
	
			break if @l == 0 && @r == @items.size-1
		}
	
		return [@opt_cost, @lower_bound]
	end

private
	def upper_bound(cost, value)
		if cost <= @budget
			if @r == @items.size-1
				value
			else
				value + (@budget - cost).to_f * @items[@r+1][1] / @items[@r+1][0]
			end
		else
			if @l == 0
				value
			else
				value + (@budget - cost).to_f * @items[@l-1][1] / @items[@l-1][0]
			end
		end
	end

	def prun
		@states.reject!{|c, v|
			next true if c - @left_cost > @budget
			next true if upper_bound(c, v) <= @lower_bound
			false
		}
		hash = Hash.new(0)
		@states.each{|c, v|
			hash[c] = v if v > hash[c]
		}
		@states = hash.to_a
	end

	def update_lower_bound
		@states.each{|c, v|	
			if c <= @budget && v > @lower_bound
				@lower_bound = v 
				@opt_cost = c
			end
		}
	end
end

def knapsack(items, budget, mode = :normal)
	cost_group = items.group_by(&:first)
	items = cost_group.map{|c, group|
		group.sort_by(&:last).last(budget / c)
	}.inject([], &:+)

	case mode
	when :normal
		return _knapsack_normal(items, budget) 
	when :core
		return _knapsack_core(items, budget)
	else
		raise "unknown mode"
	end
end

def _knapsack_normal(items, budget)
	table = (0..1).map{ Array.new(budget+1, 0) }
	for i in 0..items.size-1
		c, v = items[i]
		for j in 0..budget
			x = table[0][j]
			y = (j >= c ? table[0][j-c] + v : 0)
			table[1][j] = x > y ? x : y
		end
		table << table.shift
	end
	c = (1..budget).max_by{|i| table[0][i]}
	[c, table[0][c]]
end

def _knapsack_core(items, budget, mode = :normal)
	if mode == :drop_useless
		cost_group = items.group_by(&:first)
		items = cost_group.map{|c, group|
			group.sort_by(&:last).last(budget / c)
		}.inject([], &:+)
	end

	k = Knapsack.new(items, budget)
	k.solve
end

i = 1
loop {
	w = gets.to_i
	break if w == 0

	no_condition = 0
	n = gets.to_i
	items = []
	n.times { items << gets.split(/,/).reverse.map(&:to_i) }
	items.reject!{|c, v|
		if c == 0
			no_condition += v
			next true
		end
		false
	}
	
	c, v = knapsack(items, w, :normal)
	puts "Case #{i}:"
	puts v + no_condition
	puts c
	i += 1
}