import Control.Monad
import Data.Array.IO
import Data.List.Split

main = solveKnapsack 1

solveKnapsack i = do
    w <- readLn
    unless (w == 0) $ do
        n <- readLn
        listn <- replicateM n getTreasure
        arr <- dynamic' w list
        maxVal <- readArray arr (n,w)
        weights <- searchWeight arr maxVal
        putStrLn $ "Case "++ show i ++ ":"
        print maxVal
        print $ minimum.map snd $ weights
        solveKnapsack (i+1)

getTreasure :: IO (Int,Int)
getTreasure = do
    str <- getLine
    let [x,y] = map read.splitOn "," $ str
    return  (x,y)

list = [(60,10),(100,20),(120,30),(210,45),(10,4)] :: [(Int,Int)]

dynamic' :: Int -> [(Int,Int)] -> IO (IOArray (Int,Int) Int)
dynamic' capa items = do
    arr <- newArray ((0,0),(length items,capa)) 0 :: IO (IOArray (Int,Int) Int)
    mapM_ (\(i,(v,w)) -> do
        mapM_ (\j -> do
            val1 <- readArray arr (i-1,j)
            val2 <- readArray arr (i-1,j-w)
            when (val1 < val2+v) $ do
                writeArray arr (i,j) (val2+v)) [w..capa]) $ zip [1..] items
    return arr

searchWeight :: IOArray (Int,Int) Int -> Int -> IO [(Int,Int)]
searchWeight arr n = do
    elems <- getAssocs arr
    return $ map fst $ filter (\x -> snd x == n) elems