import scala.io.Source
import scala.collection.mutable.Map

object Main {
  def main(args: Array[String]) = {
    val lines = Source.stdin.getLines.toStream
    val inSeq = lines.drop(1).head.split(' ').map(_.toLong)

    println(dp(inSeq))
  }

  def dp(input: IndexedSeq[Long]): Long = {
    val memo = Array.ofDim[(Long, Long)](input.length + 1, input.length + 1)

    (1 to input.length).foreach { n =>
      memo(n-1)(n) = input(n-1) -> 0
    }

    (2 to input.length).foreach { area =>
      var res = Long.MaxValue
      (2 to area).foreach { tgLen =>
        // cand
        var locMin = Long.MaxValue
        var cost = 0L
        ((area - tgLen + 1) to (area - 1)).reverse.foreach { split =>
          // println(area, tgLen, split)
          var cand = memo(area - tgLen)(split)._2 + memo(split)(area)._2
          if (cand <= locMin) {
            locMin = cand
            cost = memo(area - tgLen)(split)._1 + memo(split)(area)._1
          }
          // locMin = math.min(
          //   locMin, memo((area - tgLen, split))._2 + memo((split, area))._2
          // )
        }

        // println(area - tgLen, area, locMin)
        memo(area - tgLen)(area) = cost -> (locMin + cost)
      }
    }
    memo(0)(input.length)._2
  }
}
