import Control.Monad

parse :: String -> (Int , Int)
parse xs = read $ "(" ++ xs ++ ")"

mymax :: Maybe (Int , Int) -> Maybe (Int , Int) -> Maybe (Int , Int)
mymax Nothing y = y
mymax x Nothing = x
mymax (Just x) (Just y) = Just $ if fst x == fst y then if snd x < snd y then x else y else if fst x < fst y then y else x

myplus :: (Int , Int) -> (Int , Int) -> (Int , Int)
myplus x y = (fst x + fst y , snd x + snd y)

dp :: Int -> [(Int , Int)] -> Maybe (Int , Int)
dp w []
    | w < 0 = Nothing
    | otherwise = Just (0 , 0)
dp w ((p,c):rest)
    | w < 0 = Nothing
    | otherwise = dp w rest `mymax` (myplus <$> (dp (w - c) rest) <*> Just (p , c))

solve :: Int -> [(Int , Int)] -> IO ()
solve w xs = let Just (p , c) = dp w xs in print p >> print c

main :: IO ()
main = main' 1
    where
        main' :: Int -> IO ()
        main' index = do
            w <- readLn :: IO Int
            if w == 0 then return () else do
                n <- readLn :: IO Int
                xs <- replicateM n getLine >>= return . map parse
                putStrLn $ "Case " ++ show index ++ ":"
                solve w xs
                main' $ succ index