import Data.List (sort)

type Parser = Char -> Maybe Char

median :: Integral a => [a] -> a
median xs = xs !! mid
  where len = length xs
        mid = div len 2

parseChar :: Char -> Parser
parseChar c x
  | c == x    = Nothing
  | otherwise = Just x

mapOpenClose :: Char -> Char
mapOpenClose c = case c of
  '(' -> ')'
  '[' -> ']'
  '{' -> '}'
  '<' -> '>'
  _   -> error "not element in map"

score :: [Char] -> Integer
score cs = aux 0 cs
  where aux res []   = res
        aux x (c:cs) = aux (x * 5 + (delimScore c)) cs

delimScore :: Char -> Integer
delimScore c = case c of
  ')' -> 1
  ']' -> 2
  '}' -> 3
  '>' -> 4
  _   -> 0

openDelim c = (c=='(') || (c=='[') || (c=='{') || (c=='<')
closingDelim c = (c==')') || (c==']') || (c=='}') || (c=='>')

-- Keep stack of parse functions. Apply the top one on any closing delimeter,
-- check for Just x.

parseLine :: [Char] -> String -> [Char]
parseLine closers [] = closers
parseLine closers (c:str)
  | openDelim c    = parseLine (mapOpenClose c:closers) str
  | closingDelim c = case p c of
      Just _  -> []
      Nothing -> parseLine (tail closers) str
  where p = parseChar (head closers)

solution :: [String] -> Integer
solution = median
  . sort
  . map score
  . filter (/="")
  . (map $ parseLine [])

-- main = interact $ show . solution . lines