{-# LANGUAGE ViewPatterns #-}
import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.Set as S
import Data.Ord
import Debug.Trace

main :: IO ()
main = readContents 4 >>= printRes . solve
    where
        printRes = mapM_ print

solve :: [[Int]] -> [Int]
solve ([_, _, _, k] : abcs) = check k S.empty $ pf xs0 empty
    where
        xs0 = edit $ map (sortOn Down) abcs
            where
                edit [a, b, c] = [(a, b, c)]

        check 0 _ _ = []
        check n s (pop -> Just (V (v, xxs@(_ : xs), yys@(_ : ys), zzs@(_ : zs)), h))
            | S.member key s = check n s h
            | otherwise = v : check (n - 1) (S.insert key s) i
            where
                key = (xxs, yys, zzs)
                i = pf [(xs, yys, zzs), (xxs, ys, zzs), (xxs, yys, zs)] h

        check n s (pop -> Just (V (v, _, yys@(_ : ys), zzs@(_ : zs)), h))
            | S.member key s = check n s h
            | otherwise = v : check (n - 1) (S.insert key s) i
            where
                key = ([], yys, zzs)
                i = pf [([], ys, zzs), ([], yys, zs)] h

        check n s (pop -> Just (V (v, xxs@(_ : xs), _, zzs@(_ : zs)), h))
            | S.member key s = check n s h
            | otherwise = v : check (n - 1) (S.insert key s) i
            where
                key = (xxs, [], zzs)
                i = pf [(xs, [], zzs), (xxs, [], zs)] h

        check n s (pop -> Just (V (v, xxs@(_ : xs), yys@(_ : ys), _), h))
            | S.member key s = check n s h
            | otherwise = v : check (n - 1) (S.insert key s) i
            where
                key = (xxs, yys, [])
                i = pf [(xs, yys, []), (xxs, ys, [])] h

        check n s (pop -> Just (V (v, xxs@(_ : xs), _, _), h))
            | S.member key s = check n s h
            | otherwise = v : check (n - 1) (S.insert key s) (pf [(xs, [], [])] h)
            where
                key = (xxs, [], []) 
        check n s (pop -> Just (V (v, _, yys@(_ : ys), _), h))
            | S.member key s = check n s h
            | otherwise = v : check (n - 1) (S.insert key s) (pf [([], ys, [])] h)
            where
                key = ([], yys, [])
        check n s (pop -> Just (V (v, _, _, zzs@(_ : zs)), h))
            | S.member key s = check n s h
            | otherwise = v : check (n - 1) (S.insert key s) (pf [([], [], zs)] h)
            where
                key = ([], [], zzs)

        pf xs h = foldl ff h xs
            where
                ff acc (xs, ys, zs) = push (V (sum $ map head' [xs, ys, zs], xs, ys, zs)) acc
                head' [] = -40000000000
                head' (x : _) = x 

readLine :: IO [Int]
readLine = unfoldr (fmap (second (maybe B.empty snd . B.uncons)) . B.readInt) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine

data Heap a = E | T Int a (Heap a) (Heap a)
    deriving (Show)
    
empty :: Heap a 
empty = E

null :: Heap a -> Bool 
null E = True
null _ = False

merge :: (Ord a) => Heap a -> Heap a -> Heap a
merge lh@(T _ lv la lb) rh@(T _ rv ra rb)
    | lv <= rv = makeT lv la $ merge lb rh
    | otherwise = makeT rv ra $ merge lh rb
    where
        makeT v a b
            | rank a >= rank b = T (rank b + 1) v a b
            | otherwise = T (rank a + 1) v b a
        rank (T r _ _ _) = r
        rank _ = 0
        
merge lh E = lh
merge _ rh = rh

push :: (Ord a) => a -> Heap a -> Heap a
push x = merge (T 1 x E E)

pop :: (Ord a) => Heap a -> Maybe (a, Heap a) 
pop (T _ x a b) = Just (x, merge a b)
pop _ = Nothing

fromList :: (Ord a) => [a] -> Heap a
fromList = br . fmap (\x -> T 1 x E E)
    where
        build (x : y : zs) = merge x y : build zs
        build xs = xs
        br [x] = x
        br xs = br $ build xs

newtype V = V (Int, [Int], [Int], [Int])
    deriving (Eq, Show)

instance Ord V where
    compare (V (lv, _, _, _)) (V (rv, _, _, _)) = compare rv lv

Measured memory_bytes: 3196