{-# LANGUAGE ScopedTypeVariables #-}
-- extension section
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
{-# LANGUAGE BangPatterns      #-}
{-# LANGUAGE CPP               #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TupleSections     #-}
 -- not supported extension
--{-# LANGUAGE Strict, StrictData #-}


module ContestMain where

-- @@@@@@@@@@@@@@@@@--
-- import section   --
-- @@@@@@@@@@@@@@@@@--
--    import A.B.C( function name )  ...
-- or import A.B.C 

--
import           Prelude hiding(
  getLine,
  getContents,
  lines,
  words
  )

-- standard library
import           Control.Monad.ST
import           Control.Applicative
import           Data.Char
import           Data.Foldable
import           Debug.Trace


-- bytestring
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B


-- containers
import           Data.Sequence               as S

-- deepseq


-- regex-posix


-- text
import           Data.Text.Lazy.IO as TIO
import           Data.Text.Lazy as T
import           Data.Text.Lazy.Read as TR

-- import Data.Text.IO as TIO
-- import Data.Text as T
-- import Data.Text.Read as TR



-- unordered-containers


-- vectors
import           Data.Vector.Unboxed         as  UV
import           Data.Vector.Unboxed.Mutable as MUV
import qualified Data.Vector                 as   V
import qualified Data.Vector.Mutable         as MV


-- mtl


-- @@@@@@@@@@@@@@@@@--
-- main section     --
-- @@@@@@@@@@@@@@@@@--

main :: IO ()
main = do
  print =<<  getInputAndAnser
-- main :: IO()
-- main = do
--   answer <- getInputandanser
--   putStr . show $ answer


-- @@@@@@@@@@@@@@@@@@@@@--
-- I/O DataType section --
-- @@@@@@@@@@@@@@@@@@@@@--
type Input =  (Int,Vector Int)

type Answer = Int


-- @@@@@@@@@@@@@@@@@--
-- answerSection    --
-- @@@@@@@@@@@@@@@@@--
getInput :: IO Input
getInput = do
  n <- Prelude.read . unpack <$>  gLine 
  avec <- intVectorFromLine n
  return (n,avec)
  
getAnswer :: Input -> Answer 
getAnswer = undefined
  

getInputAndAnser :: IO Answer
getInputAndAnser = do
  (!n,!avec) <- getInput
  let (residualEs, plusSum) = runST $ makeEdges n avec 
  (initFvec:: IOVector Int) <- MUV.replicate ((n+2)*(n+2)) 0
--  print residualEs
--  print initLvl
  maxFlow <- getMaxFlow residualEs initFvec (n+2)
  return $ plusSum - maxFlow
  
--
getMaxFlow :: V.Vector( Seq(Int,Int) ) -> IOVector Int -> Int -> IO Int
getMaxFlow adjs fvec size = go 0 
  where
    fidx = eToFidx size 
    go :: Int -> IO Int
    go total = do
      !ffvec <- freeze fvec 
      let lvl = level size adjs ffvec
      if (lvl ! (size-1)) < 0
        then return total
        else (do
                 !startv <-  MUV.replicate size 0
                 !newtotal <- sendFlow total startv
                 go newtotal
             )
    sendFlow :: Int -> IOVector Int -> IO Int
    sendFlow total start= do
      !flow <- sendFlow' 0 (size-1) maxBound start
      if flow > 0 
        then sendFlow (total + flow) start
        else return total
    sendFlow' :: Int -> Int -> Int -> IOVector Int -> IO Int
    sendFlow' u t wantToSend start = do
      if u == t 
        then return wantToSend 
        else do  
        !edgeNum <- MUV.read start u
        !ffvec   <- freeze fvec     
        let !adj = adjs V.! u
        if edgeNum < S.length adj then do
        let   !(v,c) = adj `S.index` edgeNum
              !lvl = level size adjs ffvec
              !flow = ffvec ! (fidx (u,v)) 
--        if   trace ( show u Prelude.++ " " Prelude.++  show v Prelude.++ " " Prelude.++show lvl Prelude.++ " " Prelude.++show flow  Prelude.++ " " Prelude.++show edgeNum) lvl ! v == (lvl ! u) + 1 && flow < c
        if  lvl ! v == (lvl ! u) + 1 && flow < c
          then do
            let currF = min wantToSend ( c - flow )
            !tempF <- sendFlow' v t currF start 
--            !tempF <- trace "tempSend!" sendFlow' v t currF start 
            if tempF > 0 
              then do
                !_ <-MUV.modify fvec (+ tempF) (fidx (u,v) )
                !_ <-MUV.modify fvec (\a -> a - tempF) (fidx (v,u) )
                return tempF
              else updateStartAndRerun
          else updateStartAndRerun
        else return 0 
          where updateStartAndRerun = do 
                  !_ <- MUV.modify start ((+) 1) u
                  sendFlow' u t wantToSend start 

--                            size (n+2)  =>  maxsize (n+2)
makeEdges :: Int -> Vector Int -> ST s ( V.Vector ( Seq (Int, Int) ) , Int )  
makeEdges n avec = do
  ( adj :: MV.STVector s ( Seq (Int,Int) ) ) <- MV.replicate (n+2) S.empty
  let
    cnst :: Int -> Int -> Int -> ST s Int
    cnst !acm !idx' !a
      | a > 0 = do
          MV.modify adj ( |> (n+1, a) ) idx
          MV.modify adj ( |> (idx, 0) ) (n+1)    
          _ <- mula (2*idx)
          return $ acm + a
      | otherwise  = do
          MV.modify adj ( |> (0, 0) ) idx
          MV.modify adj ( |> (idx, -a) ) 0
          _ <- mula (2*idx)
          return $ acm 
      | otherwise = undefined
        where idx = idx'+1
              mula !idx2' 
                | idx2' > n = return ()
                | otherwise = do
                    MV.modify adj ( |> (idx2', maxBound) ) idx
                    mula (idx2' + idx)
  plusSum <- ifoldM' cnst 0 avec 
  resAdj <- V.freeze adj
  return $ (resAdj, plusSum)


type From = Int
type To   = Int
type Size = Int
eToFidx :: Int -> (From, To) -> Int
eToFidx nVertex (!f ,!t)= nVertex * f + t

--       nvertex          adj                      flowVec      level
level :: Size -> V.Vector ( Seq (Int, Int) ) -> Vector Int -> Vector Int
level size adj flow = runST $ go (S.singleton (0:: Int) ) (UV.replicate size (-1 :: Int) // [(0,0)] )
  where 
    go :: Seq Int  -> Vector Int -> ST s (Vector Int)
    go q lvl = do
      lvl' <- thaw lvl
      go' q lvl'
    go' q lvl | S.null q = freeze lvl
              | otherwise = let (topV :< q') = viewl q in
                  do
                    nowLvl <- MUV.read lvl topV
                    let adjs = (adj V.! topV)
                        leveling oldQ (to, c) = do
                          oldLvl <-  MUV.read lvl to
                          if oldLvl < 0 && ( (flow ! (eToFidx size (topV,to) )) < c)
                            then (do 
                                     _ <- write lvl to (nowLvl+1)  
                                     return $ oldQ |> to
                                 )
--                            else   trace (show to Prelude.++ " " Prelude.++ show oldLvl ) $ return oldQ                          
                            else  return oldQ                          
                    newq <- foldlM leveling q' adjs 
                    go' newq lvl
        


-- @@@@@@@@@@@@@@@@@@@@@@@@@@--
-- question unique section    --
-- @@@@@@@@@@@@@@@@@@@@@@@@@@--





-- @@@@@@@@@@@@@@@@@--
-- util section     --
-- @@@@@@@@@@@@@@@@@--

-- standard Input Function
gLine :: IO Text
gLine = getLine

gContents :: IO Text
gContents = getContents

-- intVectorFromline 5  ("1 2 3 4 5") -> vector <1,2,3,4,5> 
intVectorFromLine ::Int -> IO ( Vector Int )
intVectorFromLine n = UV.unfoldrN n (B.readInt.B.dropWhile isSpace) <$> B.getLine

pairFromLine :: IO (Int,Int)
pairFromLine = do
  v <- intVectorFromLine 2
  return ( v ! 0, v ! 1)

generatePairVectorFromLine :: Int -> IO ( Vector (Int, Int) )
generatePairVectorFromLine n = generateM n (const pairFromLine)
