INF = 1<<60
n = gets.to_s.to_i
a = gets.to_s.split.map { |v| v.to_i }

dp = Array.new(n) { |i| Array.new(n) { |j| i == j ? 0 : INF } }
cs = a.each_with_object([0]) { |v, b| b << b[-1] + v }

1.upto(n-1) do |j|
  0.upto(n-1-j) do |i|
    lo = i
    hi = i + j
    # pp [lo,hi]
    lo.upto(hi-1) do |mid|
      dp[lo][hi] = [
        dp[lo][hi],
        dp[lo][mid] + dp[mid+1][hi] + cs[hi+1] - cs[lo]
      ].min
    end
  end
end

pp dp[0][-1]
