import Data.Ord
import Data.List

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) = minimum_w $ maximum_vs $ (pack 0 0) treasures
 where
  minimum_w = head . sortBy (comparing snd)
  maximum_vs vws = filter ((== maximum (map fst vws)) . fst) vws
  pack v w [] = [(v,w)]
  pack v w ([vt,wt]:ts)
   | w+wt > max_weight = pack v w ts
   | otherwise = concat [pack v w ts, pack (v+vt) (w+wt) ts]