def main(input = $stdin)
  count = 1
  while (w = input.gets.to_i) != 0
    n = input.gets.to_i
    goods = []
    n.times do
      goods << input.gets.split(",").map(&:to_i)
    end
    values = Array.new(w + 1)
    values[0] = 0
    goods.each{|good|
      (-good[1] - 1).downto(-w - 1){|idx|
        if values[idx] and (!values[idx + good[1]] or values[idx] + good[0] > values[idx + good[1]])
          values[idx + good[1]] = values[idx] + good[0]
        end
      }
      
    }
    puts "Case #{count}:"
    puts values.max_by{|i|i.to_i}
    puts values.index(values.max_by{|i|i.to_i})
    count += 1
  end
end
main