import Data.Tuple
import Data.List
import Data.List.Split
import Data.Graph

main :: IO ()
main = do
  input <- readFile "input"
  let ls = lines input
  let (cond, pages) = splitBy ls ""
  let cs = map (toPair . map readInt) $ map (splitOn "|") cond
  let ps = map (map readInt) $ map (splitOn ",") pages
  let incorrect = filter (not . isWellOrdered cs) ps
  let fixed = map (fixOrder cs) incorrect
--  print fixed
--  mapM_ print incorrect
  print (sum (map median fixed))

fixOrder allEdges verts =
  let edges = filter (\(a,b) -> elem a verts && elem b verts) allEdges
      g = buildG (minimum verts, maximum verts) edges
      sorted = filter (\n -> elem n verts) (topSort g)
  in sorted

median xs = xs!!(div (length xs) 2)

isWellOrdered conds xs =
  let pairs = map swap (orderedPairs xs)
  in and $ map (\p -> notElem p conds) pairs

splitBy :: Eq a => [a] -> a -> ([a], [a])
splitBy xs sep =
  case elemIndex sep xs of
    Nothing -> (xs, [])
    Just i -> (take i xs, drop (i+1) xs)

toPair [a,b] = (a,b)

readInt :: String -> Int
readInt = read

orderedPairs (x:[]) = []
orderedPairs (x:xs) = [(x,y) | y <- xs] ++ orderedPairs xs