
ans = []
index = 0
while true
  v = gets.to_i
  break if v.zero?
  index += 1
  count = gets.to_i
  arr_v = []; arr_w = []

  count.times do |i|
    value, key = gets.split(",").map(&:to_i)
    arr_v << value
    arr_w << key
  end

  max_key = 0
  max_value = 0

  dp = Hash.new
  dp[0] = 0

  count.times do |ind|
    dp_tmp = dp.clone

    dp.each do |key, value|
      total_key = key + arr_v[ind]
      total_value = value + arr_w[ind]

      if !dp_tmp.has_key?(total_key)
        dp_tmp[total_key] = total_value
      elsif dp_tmp.has_key?(total_key) && total_value <= dp_tmp[total_key]
        dp_tmp[total_key] = total_value
      end

      if v >= total_value && total_key > max_value
        max_key = total_key
        max_value = total_value
      end
    end

    dp = dp_tmp
  end
  ans << [ "Case #{index}:", max_key, max_value ]
end

ans.each do |arr|
  arr.each do |val|
    puts val
  end
end