import Data.List
import Data.IntMap (singleton, (!), keys, elems, unionWith, filterWithKey, mapKeys)
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::String->Int) 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 (singleton 0 0) treasures
 where
  dp im [] = (im!k, k)
   where k = minimum $ keys $ M.filter (== (maximum $ elems im)) im
  dp im ([v,w]:vws) = dp (unionWith max im (filterWithKey (\k _-> k<=max_weight) im')) vws
   where im' = M.map (+v) $ mapKeys (+w) im