cases = 1
while (weight = gets.to_i) != 0
  arr = Array.new(weight + 1,0)
  n = gets.to_i
  treasure = Array.new
  n.times do
    treasure << gets.split(",").map(&:to_i)
  end
  treasure.sort_by!{|item|item[1]}
  for i in treasure
    if arr[i[1]] < i[0]
      arr[i[1]] = i[0]
    end
    for j in i[1] + 1...arr.length
      if arr[-j] != 0 and arr[i[1] - j] < i[0] + arr[-j] and arr.length - j != i[1]
        arr[i[1] - j] = i[0] + arr[-j]
      end
    end
  end
  puts "Case #{cases}:", arr.max, arr.index(arr.max)
  cases += 1
end