let N = Int(readLine()!)!

let a = readLine()!.split(separator: " ").map { Int($0)! }

var dp: [[Int]] = .init(repeating: .init(repeating: -1, count: N), count: N)
var sum: [Int] = .init(repeating: 0, count: N+1)
for i in 1..<sum.count {
  sum[i] = sum[i-1] + a[i-1] 
}

func backtrack(_ l: Int, _ r: Int) -> Int {
  if l == r {
    return 0
  }
  if dp[l][r] != -1 {
    return dp[l][r]
  }
  
  var ans = sum[r+1] - sum[l]
  var minCost = Int.max
  for i in l..<r {
    minCost = min(minCost, backtrack(l, i) + backtrack(i+1, r))
  }
  dp[l][r] = ans + minCost
  return dp[l][r]
}
print(backtrack(0, N-1))