import Control.Monad (replicateM)
import Data.Array (Array,listArray,accum,assocs,bounds,inRange)
import Data.List (foldl')
import Data.List.Split (splitOn)

type Weight = Int
type Price = Int
type Table = Array Weight Price

main = main' 1
    where
    main' cn = do
        mw <- read `fmap` getLine
        if mw == 0 then return () else do
            n <- read `fmap` getLine
            wps <- (map ((\[p,w]->(w,p)) . map read . splitOn ","))
                `fmap` replicateM n getLine

            let
               (aw,ap) = solve mw wps

            putStrLn ("Case " ++ (show cn) ++ ":")
            print ap
            print aw
            
            main' (cn+1)

solve :: Weight -> [(Weight,Price)] -> (Weight,Price)
solve mw wps = head $ isMaxPrice $ assocs wps'
    where
    wps' = foldl' update (listArray (0,mw) [0,0..]) wps
    isMaxPrice wps = mp `seq` filter (\(_,p) -> p == mp) wps
        where
        mp = maximum $ map snd wps

update :: Table -> (Weight,Price) -> Table
update wps (w',p') = accum max wps wps'
    where
    wps' = filter (\(w,_) -> inRange (bounds wps) w) $
            map (\(w,p) -> (w+w', p+p')) $ assocs wps