#include<iostream>
#include<algorithm>
#define INF 0x7fffffff
#define int long long
#define re register
#define zhuang_bi ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
using namespace std;

const int N = 1005;

int n;
int a[N];
int dp[N][N];
int sum[N];

signed main(){
	zhuang_bi
	cin>>n;
	for(re int i = 1;i <= n;i ++){
		cin>>a[i];
		sum[i] = sum[i - 1] + a[i];
		dp[i][i] = a[i];
	}
	for(re int len = 1;len <= n;len ++){
		for(re int i = 1;i + len <= n;i ++){
			int j = i + len;
			dp[i][j] = INF;
			for(re int k = i;k <= j;k ++){
				dp[i][j] = min(dp[i][j],dp[i][k] + dp[k + 1][j]);
			}
			dp[i][j] += sum[j] - sum[i - 1];
		}
	}
	cout<<dp[1][n];
    return 0;
}