local n=io.read("n")
local a={[0]=0}
for i=1,n do
    a[i]=a[i-1]+io.read("n")
end

local dp={}
local flag={}
for i=1,n do
    dp[i]={}
    flag[i]={}
    for j=1,n do
        dp[i][j]=0
    end
end

local INF=10^20
local function solve(i,j)
    if flag[i][j] then
        return dp[i][j]
    end
    flag[i][j]=true
    if i==j then
        return 0
    end
    local min=INF
    for k=i,j-1 do
        min=math.min(min,solve(i,k)+solve(k+1,j))
    end
    dp[i][j]=min+a[j]-a[i-1]
    return dp[i][j]
end

print(solve(1,n))