#!/usr/bin/runhaskell
import Data.List

type Number = Int

data Machine = Machine {day       :: Number
                       ,buy       :: Number
                       ,sell      :: Number
                       ,profit    :: Number
                       ,maxprofit :: Number} deriving Show

data Case = Case {machines :: [Machine]
                 ,capital  :: Number
                 ,days     :: Number} deriving Show

type Plan = [Bool]

numSplit :: String -> [[Number]]
numSplit str = [[read num | num <- words line] | line <- lines str]


finalCapital :: Case -> [Machine] -> Plan -> Maybe Number
finalCapital thecase machines plan =
  alldays + finalday
  where
    (alldays, finalslot) =
      foldl' addCapital (Just (capital thecase), Nothing) $ zip plan machines
    finalday =
      if finalslot == Nothing then
        0
      else
        (days thecase + day finalslot)*profit finalslot + sell finalslot

    addCapital :: (Maybe Number, Maybe Machine)
                  -> (Bool, Machine)
                  -> (Maybe Number, Maybe Machine)
    addCapital (Nothing, _) _ = (Nothing, Nothing)
    addCapital (Just currcapital, Nothing) (action, machine)
      | currcapital < buy machine = Nothing
      | otherwise                 = Just 2

    addCapital (Just currcapital, Just slot) (action, machine)
      | action = Just (currcapital + profit machine)
      | otherwise = Just 0


makeMachine :: Number -> [Number] -> Machine
makeMachine days line = Machine mDay mBuy mSell mProfit mMaxprofit
  where
    mMaxprofit = (days - mDay)*mProfit - mBuy + mSell
    [mDay, mBuy, mSell, mProfit] = line

groupCases :: [[Number]] -> [Case]
groupCases [] = []
groupCases (header:rest) =
  Case machines capital days : groupCases nextCase
  where
    (machinelist, nextCase) = splitAt n rest
    [n, capital, days] = header
    machines = sortBy (\m1 m2 -> day m1 `compare` day m2)
               $ map (makeMachine capital) machinelist

parseInput :: String -> [Case]
parseInput input = groupCases (numSplit input)

solver :: Case -> Number
solver thecase = capital thecase + sum (map maxprofit (machines thecase))

processCases input =
  unlines $
  map (\(n,m) -> "Case " ++ show n ++ ": " ++ show m)
  (zip  [1, 2..]  (map solver (parseInput input)))

main = interact processCases