{- Author: Robin Nittka -}
{-# OPTIONS_GHC -O2 #-}

module Main
	where

import System.IO
import Data.Array
import Data.Array.ST
import Control.Monad.ST

type RemAr = Array (Int,Int) Integer
type STAr s = STArray s (Int,Int) Integer

remainders :: [Integer] -> RemAr
remainders list = array ((0,0),(len,len)) [ ((i,j), subsum i j list) | i <- [0..len], j <- [i..len] ]
	where
		len = length list
		subsum i j = sum . take (j-i) . drop i

every2 :: [a] -> [a]
every2 [] = []
every2 [_] = []
every2 (_:x:xs) = x:every2 xs

update :: RemAr -> STAr s -> Int -> Int -> ST s ()
update remain table k n = do
	col <- sequence [readArray table (k-1,m) | m <- [1..n]]
	writeArray table (k,n) $ minimum $ map ( \(m,v) -> v + (toInteger $ k+n) * remain ! (m,n) ) $ zip [1..] col

solve :: [Integer] -> Integer
solve input = runST $ do
	let len = length input
	let remain = remainders input
	table <- newArray_ ((1,1),(len,len))
	sequence_ [writeArray table (1,i) $ (toInteger $ i+1) * remain ! (0,i) | i <- [1..len]]
	sequence_ [update remain table k n | k <- [2..len], n <- [1..len]]
	readArray table (len,len)

main :: IO ()
main = do
	file <- openFile "elias.in" ReadMode
	hGetContents file >>= mapM_ (print . solve . map read . words) . every2 . lines
