import Data.IntMap (keys, elems, adjust, fromList, (!))
import qualified Data.IntMap as M

splitOn c xs
 | null xs = []
 | head xs == c = splitOn c (tail xs)
 | otherwise = (takeWhile (/= c)) xs : splitOn c (dropWhile (/= c) xs)

main = interact $ unlines . numbering . map (show' . thief) . read' . lines
 where
  read' ("0":_) = []
  read' (w:n:xs) = (read w, parse_vw $ take (read n) xs) : read' (drop (read n) xs)
   where parse_vw = map (map read . splitOn ',')
  show' (v,w) = show v ++ "\n" ++ show w
  numbering = zipWith (++) ["Case " ++ show n ++ ":\n" | n<-[1..]] 

thief (max_weight, treasures) = dp (fromList $ zip [0..max_weight] (repeat 0)) treasures
 where
  dp im [] = (im!k, k)
   where k = minimum $ keys $ M.filter (== (maximum $ elems im)) im
  dp im ([v,w]:vws)
   | (im!w) > v = dp im vws
   | otherwise = dp (update_im keys_update $ adjust (max v) w im) vws
   where
    im_nz = M.filter (/= 0) im
    keys_update = map (+w) (filter (>w) $ keys $ M.filter (>0) im)
    update_im [] im = im
    update_im (k:ks) im = update_im ks (adjust (max (im!(k-w) + v)) k im)