require 'pp'
N = ARGF.gets.to_i
A = ARGF.gets.split(" ").map(&:to_i)

dp = Array.new(N) do Array.new(N, 1000) end
weight = Array.new(N) do Array.new(N, 0) end

def pri(weight)
  puts weight.map{|r| r.map{|x| "%04d"%x}.join(",")}.join("\n")
end

for w in 1..N
  for l in 0..N-w
    r = l+w-1
    if w == 1
      dp[l][r] = 0
      weight[l][r] = A[l]
      next
    end

    if w == 2
      dp[l][r] = A[l] + A[r] # dp[l][l+1]
      weight[l][r] = A[l] + A[r]
      next
    end

    weight[l][r] = weight[l+1][r] + A[l]

    for wl in 1...w
      n = dp[l][l+wl-1] + dp[l+wl][r] + weight[l][l+wl-1] + weight[l+wl][r]

      if dp[l][r] > n
        dp[l][r] = n
      end
    end
  end
end

puts dp[0][N-1]
