class Solver
  @@i = 0

  def initialize(weight)
    @@i += 1

    @weight = weight
    @n = gets.to_i
    @item = Array.new
    @n.times do
      @item << gets.chomp.split(?,).map(&:to_i)
    end
  end

  def solve
    puts "Case #{@@i}:"
    puts _solve(0)
  end

  private

  def _solve(i, weight = @weight)
    @memo ||= Hash.new{Hash.new}
    @memo[i][weight] ||= if i == @n
      [0, @weight - weight]
    elsif weight < @item[i].last then
      _solve(i + 1, weight)
    else
      [
        (s = _solve(i + 1, weight - @item[i].last); s[0] += @item[i].first; s),
        _solve(i + 1, weight)
      ].max do |a, b|
        if a.first == b.first then
          b.last <=> a.last
        else
          a.first <=> b.first
        end
      end
    end
  end
end

until (weight = gets.to_i) == 0
  solver = Solver.new(weight)
  solver.solve
end