1.upto(50) { |cnt|
  $aw = gets.to_i
  break if $aw == 0

  $an = gets.to_i
  $v,$w = Array.new($an), Array.new($an)
  0.upto($an - 1) { |i|
    $v[i], $w[i] = gets.split(",").map(&:to_i)
  }

  $dv, $dw = Array.new($an){Array.new($aw + 1)}, Array.new($an){Array.new($aw + 1)}
  def calc(i, j)
    return 0 if i >= $an
    return $dv[i][j], $dw[i][j] if $dv[i][j] != nil && $dw[i][j] != nil

    res = 0
    if j < $w[i]
      res = calc(i + 1, j)
    else
      d1 = calc(i + 1, j)
      d2 = calc(i + 1, j - $w[i])
      if d1[0] >= (d2[0] + $v[i])
        res = d1[0], d1[1]
      else
        res = d2[0] + $v[i], d2[1] + $w[i]
      end
    end
    $dv[i][j], $dw[i][j] = res
    #puts "$dv[#{i}][#{j}], $dw[#{i}][#{j}] = #{res}"
    return res
  end

  puts "Case #{cnt}:"
  ans = calc(0, $aw)
  puts ans[0]
  puts ans[1]
}