{-# LANGUAGE BangPatterns, MultiWayIf #-}
import Control.Arrow
import Control.Monad.Fix
import Control.Monad.ST
import Data.Int
import Data.Foldable
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Mutable as VM
import qualified Data.ByteString.Char8 as B
import Debug.Trace

constructN' :: Int -> (V.Vector a -> a) -> V.Vector a
constructN' !n !f = runST $ do
  v  <- VM.new n
  v' <- V.unsafeFreeze v
  fill v' 0
 where
  fill !v i | i < n =
    let x = f $ V.unsafeTake i v
    in  x `seq` do
          v' <- V.unsafeThaw v
          VM.unsafeWrite v' i x
          v'' <- V.unsafeFreeze v'
          fill v'' (i + 1)
  fill v _ = return v

solve :: Int -> VU.Vector Int -> Int
solve !n !an = fst $ VU.head $ V.last dp
 where
  dp :: V.Vector (VU.Vector (Int, Int))
  dp = constructN'
    n
    (\(!vec) ->
      let !i = V.length vec
      in  VU.map
              (\(!j) -> if i == 0
                then let z = an VU.! j in (0, z)
                else minimum
                  [ let (c1, s1) = vec V.! k VU.! j
                        (c2, s2) = vec V.! (i - k - 1) VU.! (j + k + 1)
                        s        = s1 + s2
                    in  (c1 + c2 + s, s)
                  | k <- [0 .. i - 1]
                  ]
              )
            $ VU.fromList [0 .. n - i - 1]
    )

main = do
  let readInt :: Integral a => B.ByteString -> Maybe (a, B.ByteString)
      readInt = fmap (first fromIntegral . second B.tail) . B.readInt

  n  <- (\vec -> (vec VU.! 0)) . VU.unfoldrN 1 readInt <$> B.getLine
  an <- VU.unfoldrN n readInt <$> B.getLine
  print $ solve n an
