count = 0
until (w = gets.to_i) == 0
    count += 1
    items = []
    (n = gets.to_i).times do
        items << gets.split(',').map(&:to_i)
    end

    dp = [[0]*(w+2)]
    n.times do
        dp << Array.new(w+2, 0)
    end

    n.times do |x|
        (w+1).times do |y|
            if items[x][1] > y
                dp[x+1][y+1] = dp[x][y+1]
            else
                dp[x+1][y+1] = [ dp[x][y+1], dp[x][y+1-items[x][1]] + items[x][0] ].max
            end
        end
    end
    puts "Case #{count}:", dp[n][w+1]
    (w+2).times do |i|
        if dp[n][i] == dp[n][w+1]
            puts i-1
            break
        end
    end
end