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

/// dp[leftSlime][rightSlime]
/// leftSlime〜rightSlimeを合体させる最小コスト
var dp = Array(repeating: Array(repeating: Optional<Int>.none, count: N), count: N)

func getMinimumCost(from leftSlime: Int, through rightSlime: Int) -> Int {
    /// 区間内にスライムが1体以上いること
    guard leftSlime < rightSlime else {
        /// 区間内にスライムがいない、つまり操作が発生しないのでコスト0
        dp[leftSlime][rightSlime] = 0
        return 0
    }

    /// 既に計算済みならそれを返す
    guard dp[leftSlime][rightSlime] == nil else { return dp[leftSlime][rightSlime]! }

    var cost = Int.max
    var size = a[leftSlime]
    for i in stride(from: leftSlime, to: rightSlime, by: 1) {
        let cost0 = getMinimumCost(from: leftSlime, through: i)
        let cost1 = getMinimumCost(from: i + 1, through: rightSlime)
        cost = min(cost, cost0 + cost1)

        size += a[i + 1]
    }

    dp[leftSlime][rightSlime] = cost + size
    return cost + size
}

print(getMinimumCost(from: 0, through: N - 1))
