n = gets.to_i
a = gets.split.map(&:to_i)
size=Array.new(n){Array.new(n,-1)}
cost=Array.new(n){Array.new(n,0)}
n.times do |i|
	size[i][i] = a[i]
end

1.upto(n-1) do |i| #幅
	(n-i).times do |j| #左端
		sMin,cMin = 10**20,10**20
		i.times do |k|
			s = size[j][j+k] + size[j+k+1][i+j]
			c = s + cost[j][j+k] + cost[j+k+1][i+j]
			if cMin > c
				cMin = c
				sMin = s
			end
		end
		size[j][i+j] = sMin
		cost[j][i+j] = cMin
	end
end
#p size
#p cost
p cost[0][n-1]