import Control.Monad
import Control.Monad.ST
import qualified Data.ByteString.Char8 as C
import Data.List
import Data.Maybe
import Data.STRef
import Data.Vector.Unboxed ((!))
import qualified Data.Vector.Unboxed as U

main = C.interact $ put . sol . get

get = U.unfoldr (C.readInt . C.dropWhile (<'0'))

put = C.pack . show

sol v = if e then -1 else f
  where
  n = v!0
  a = U.drop 1 v
  e = isJust $ find (uncurry (>)) [(a!(i*n+j),a!(i*n+k)+a!(k*n+j)) |
    i <- [0..n-2], j <- [i+1..n-1], k <- [0..n-1], k/=i, k/=j]
  f = runST $ do
    d <- newSTRef 0
    forM_ [0..n-2] $ \i ->
      forM_ [i+1..n-1] $ \j -> do
        let e' = isNothing $ find (uncurry (==))
              [(a!(i*n+j), a!(i*n+k) + a!(k*n+j)) | k <- [0..n-1], k/=i, k/=j]
        when (e') $ modifySTRef' d (+ a!(i*n+j))
    readSTRef d