i = 1
until (furoshiki = $<.gets.to_i).zero?
  table = {0 => 0}
  Array.new($<.gets.to_i) {$<.gets.split(",").map(&:to_i)}.each do |v, w|
    h = Hash.new(0)
    table.each {|key, value| h[key + w] = table[key] + v if key + w <= furoshiki}
    table.merge!(h) {|k, v1, v2| [v1, v2].max}
  end
  p table
  m = table.values.max
  max = table.select {|k, v| v == m}.sort {|a, b| a[0] <=> b[0]}.first
  puts "Case #{i}:", max[1], max[0]
  i += 1
end
