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

main = main' 1

main' c = do
  w <- readLn :: IO Int
  when (w /= 0) $ do
    n <- readLn :: IO Int
    xs <- input n (map read . splitOn ",") :: IO [[Int]]
    putStrLn $ "Case " ++ show c ++ ":"
    mapM_ print $ solve w n xs
    main' (c+1)

solve :: Int -> Int -> [[Int]] -> [Int]
solve w n xs = [arr ! (n,w), ttlw arr (n, w)]
  where
    arr = foldl (dp xs) (listArray ((0,0),(n,w)) (repeat 0)) idx
    idx = [(i,j) | i <- [0..n-1], j <- [1..w]]

dp :: [[Int]] -> Array (Int,Int) Int -> (Int,Int) -> Array (Int,Int) Int
dp wv arr (i,j) = arr // [((i+1,j), max v1 v2)]
  where
    v1 = arr ! (i,j)
    v2 = if j >= wv !! i !! 1 then arr ! (i,j - wv !! i !! 1) + wv !! i !! 0 else v1

ttlw :: Array (Int,Int) Int -> (Int,Int) -> Int
ttlw arr (n, w)
  | v1 == v2 = ttlw arr (n, (w-1))
  | otherwise = w
  where
    v1 = arr ! (n,w)
    v2 = arr ! (n,w-1)

input :: Int -> (String -> a) -> IO [a]
input n f = map f <$> replicateM n getLine